[Rule] VERTEX COVER to DIRECTED HAMILTONIAN CIRCUIT

[isPANN]

Source: VERTEX COVER (MinimumVertexCover)
Target: DIRECTED HAMILTONIAN CIRCUIT (HamiltonianCircuit, directed graph variant)

Motivation: This is the classic Karp/G&J reduction establishing NP-completeness of (directed) HAMILTONIAN CIRCUIT via gadget construction from VERTEX COVER. It is one of the foundational reductions in Chapter 3 of Garey & Johnson, enabling downstream reductions to HAMILTONIAN PATH, TSP, and other tour/path problems.

Reference: Garey & Johnson, Computers and Intractability, Theorem 3.4, pp. 56–60; Karp 1972

GJ Source Entry

GT38 DIRECTED HAMILTONIAN CIRCUIT
INSTANCE: Directed graph G = (V,A).
QUESTION: Does G contain a directed Hamiltonian circuit, that is, a directed cycle that includes each vertex in V exactly once?
Reference: [Karp, 1972]. Transformation from VERTEX COVER (cf. Chapter 3). Remains NP-complete for planar directed graphs with each vertex having in-degree ≤ 2 and out-degree ≤ 2 [Plesnik, 1979].

Reduction Algorithm

The full construction is given in Garey & Johnson, Theorem 3.4 (pp. 56–60). This is the same VC→HC gadget construction described in R07, adapted for directed graphs:

Summary:
Given a MinimumVertexCover instance (G = (V, E), K) with n = |V| vertices and m = |E| edges, construct a directed HamiltonianCircuit instance G' = (V', A') as follows:

1. Selector vertices: Add K vertices a₁, ..., a_K representing "slots" for the K cover vertices.

2. Cover-testing gadgets: For each edge e = {u, v} ∈ E, add 12 vertices — (u,e,1)...(u,e,6) and (v,e,1)...(v,e,6) — connected by directed arcs forming two directed 6-chains with directed cross-links. The gadget enforces exactly three valid traversal modes: (a) only u-side traversed, (b) both sides traversed, (c) only v-side traversed. Each mode ensures that at least one endpoint of e is "selected" by the circuit.

3. Vertex path arcs: For each vertex v ∈ V, chain together its incident gadgets using directed arcs {(v, e_{v[i]}, 6) → (v, e_{v[i+1]}, 1)}, forming a single directed path through all gadget-vertices labeled with v.

4. Selector connection arcs: For each selector aᵢ and each vertex v ∈ V, add directed arcs aᵢ → (v, e_{v[1]}, 1) and (v, e_{v[deg(v)]}, 6) → aᵢ, connecting the selector to both endpoints of v's vertex path.

5. Solution extraction: A directed Hamiltonian circuit in G' visits all vertices exactly once. The K selector vertices divide the circuit into K directed sub-paths, each corresponding to a vertex v ∈ V. The K selected vertices form a vertex cover.

Vertex count: 12m + K
Arc count: 14m + (2m − n) + 2Kn = 16m − n + 2Kn

Size Overhead

Symbols:

• n = num_vertices of source MinimumVertexCover instance (|V|)
• m = num_edges of source MinimumVertexCover instance (|E|)
• K = cover size bound

Target metric	Polynomial
num_vertices	12 * num_edges + K
num_arcs	16 * num_edges - num_vertices + 2 * K * num_vertices

Derivation:

• Vertices: 12 per edge gadget + K selector vertices → 12m + K
• Arcs: 14m (gadget internal) + (2m − n) (vertex path chains) + 2Kn (selector connections) = 16m − n + 2Kn

Validation Method

• Closed-loop test: reduce a small MinimumVertexCover instance (G, K) to directed HamiltonianCircuit G', solve G' with BruteForce, then verify that a directed Hamiltonian circuit exists iff G has a vertex cover of size ≤ K.
• Test with a triangle graph (K₃): minimum VC size 2; verify HC exists with K=2, not with K=1.
• Test with a star graph S₃ (center + 3 leaves): minimum VC is 1 (the center); verify HC exists with K=1.
• Verify vertex and arc counts match formulas.

Example

Source instance (MinimumVertexCover):
Graph G with 3 vertices {0, 1, 2} forming a triangle K₃:

• Edges: e₀={0,1}, e₁={0,2}, e₂={1,2}
• n = 3, m = 3, K = 2
• Minimum vertex cover: {0, 1} (covers all edges)

Constructed target instance (Directed HamiltonianCircuit):

• Vertex count: 12 × 3 + 2 = 38 vertices
• Arc count: 16 × 3 − 3 + 2 × 2 × 3 = 48 − 3 + 12 = 57 arcs

Solution mapping (vertex cover {0, 1}, assigning a₁↔0, a₂↔1):

• For e₀={0,1}: both in cover → mode (b): traverse all 12 vertices
• For e₁={0,2}: only 0 in cover → mode (a): traverse 0-side (6 vertices)
• For e₂={1,2}: only 1 in cover → mode (a): traverse 1-side (6 vertices)
• Directed circuit: a₁ → [gadgets for vertex 0] → a₂ → [gadgets for vertex 1] → a₁
• All 38 vertices visited exactly once ✓

References

• Karp, R. M. (1972). Reducibility among combinatorial problems. In Miller, R. E. and Thatcher, J. W., editors, Complexity of Computer Computations, pp. 85–103. Plenum Press.
• Garey, M. R. and Johnson, D. S. (1979). Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman. Problem GT38, Theorem 3.4.
• Plesnik, J. (1979). The NP-completeness of the Hamiltonian cycle problem in planar digraphs with degree bound two. Information Processing Letters, 8(4):199–201.