Motivation
A Hamiltonian path visits every vertex exactly once. A Hamiltonian cycle closes such a visit into a loop. Their definitions are close, but a reduction must preserve every yes and no instance, including the endpoints and the direction of edges. A similar issue arises in traveling-salesperson problems: making missing graph edges expensive can encode a Hamiltonian cycle, but the metric triangle inequality constrains how expensive those edges may be.
We will prove explicit graph transformations and use them to derive decision and approximation consequences. As a stated prerequisite, we use the standard NP-completeness of directed Hamiltonian cycle on simple loopless directed graphs with at least two vertices. This chapter does not prove that prerequisite from SAT. It does prove each transformation that follows from it and gives certificates for the target decision problems.
Definitions
Definition 4.5.1
(Hamiltonian paths and cycles)
A directed Hamiltonian cycle is a cyclic ordering of all vertices in which each consecutive ordered pair, including the closing pair, is a directed edge. A directed Hamiltonian path is a vertex sequence visiting every vertex once and respecting edge directions. In an undirected simple graph, the corresponding path and cycle use undirected edges. For undirected cycles we work with at least three vertices and require a simple cycle.
Definition 4.5.2
(Traveling-salesperson instances, tours and metric costs)
A symmetric traveling-salesperson instance here is a complete undirected graph on vertices with nonnegative integer edge costs. A tour is a Hamiltonian cycle, and its cost is the sum of its edge costs. A metric instance additionally satisfies for every three distinct vertices. The decision version asks whether some tour costs at most an integer threshold.
Theorem 4.5.3
(Paths and undirected cycles)
Directed Hamiltonian cycle reduces in polynomial time to directed Hamiltonian path and to undirected Hamiltonian cycle. The constructions below map yes instances to yes instances and no instances to no instances.
Theorem 4.5.4
(Tours with costs one and two)
Undirected Hamiltonian cycle on vertices reduces to metric traveling-salesperson decision with costs in and threshold . For any fixed rational , a polynomial-time -approximation for arbitrary nonnegative symmetric tour costs would imply a polynomial-time algorithm for undirected Hamiltonian cycle.
The proofs of both theorems are given in the construction sections below.
Directed cycle to directed path
Choose one vertex in the directed graph. Replace it by a new start and a new finish . Redirect each original edge to , and each edge to . Keep every edge between other vertices. Add no edge into and no edge out of .
Proof
(Splitting a vertex preserves Hamiltonicity)
If the original graph has a Hamiltonian cycle, start it at and replace that occurrence by at the beginning and at the end. This gives a Hamiltonian path in the new graph. Conversely, any Hamiltonian path in the new graph must start at , because has no incoming edge, and must end at , because has no outgoing edge. Replacing the two endpoints by the single vertex closes a directed Hamiltonian cycle in the original graph. All other vertices are visited exactly once, and every redirected edge corresponds to an original edge.
The graph grows by one vertex and at most a linear number of redirected edges. The construction does not assume that an arbitrary Hamiltonian path in the original graph can be closed; it builds endpoints that represent the two sides of a single original vertex.
Concept lensStructural
A Hamiltonian cycle as one cycle of a permutation
Record a directed Hamiltonian cycle by its successor map , sending each vertex to the vertex after it. Then is a bijection of the vertex set with an edge for every , and has a single cycle through all vertices; conversely, such a is a Hamiltonian cycle. Dropping the single-cycle condition leaves a disjoint union of directed cycles covering every vertex, which is an ordinary bipartite perfect-matching problem. The hardness lies entirely in forcing one cycle.
Directed cycle to undirected cycle
For each directed vertex , create three undirected vertices and internal edges and . For every directed edge , add an undirected edge . No other edges are added.
Proof
(Correctness of the gadget construction)
A directed Hamiltonian cycle gives an undirected one: traverse each gadget from its in-vertex through its middle to its out-vertex, and take the edge representing each directed transition. Conversely, every Hamiltonian cycle in the constructed undirected graph must use both internal edges at every middle vertex, since that vertex has degree two. It therefore traverses each gadget as a contiguous in–middle–out path, either forward or backward.
Every external edge joins an out-vertex to an in-vertex. If a gadget is traversed forward, from in to out, the cycle leaves it at its out-vertex through an external edge and enters the next gadget at its in-vertex, so that gadget is also traversed forward. The same argument shows that a backward traversal is followed by a backward one. Hence all gadgets are traversed in the same direction, and reversing the whole cycle if necessary we may assume that all are forward.
Each external edge used is then for an original directed edge . Contracting gadgets yields a directed Hamiltonian cycle. The gadget contains vertices and edges, so the transformation is polynomial. Directed loops were excluded; antiparallel directed edges produce distinct undirected external edges between different gadget endpoints.
Proof X-ray
Where degree two and the in-out pattern are used
The proof has two independent forcing steps. First, the middle vertex has degree two, so a Hamiltonian cycle must use both of its internal edges; this makes each gadget a contiguous in-middle-out path and prevents the cycle from entering and leaving a gadget through the same endpoint. Second, external edges join only out-vertices to in-vertices, so leaving a gadget at its out-vertex forces the next entry to be at an in-vertex, and the traversal direction cannot flip between gadgets.
Both steps are needed. If the middle vertex were removed, a cycle could use two external edges at one in-vertex, a move with no directed counterpart. The argument closes by reading each external edge of the cycle as a directed edge , which gives a directed cycle through every original vertex exactly once.
Both target problems lie in NP: a proposed vertex sequence can be checked for the required vertices, distinctness and consecutive edges in polynomial time. Together with the stated directed-cycle prerequisite, the reductions prove NP-completeness of directed Hamiltonian path and undirected Hamiltonian cycle under these conventions.
From Hamiltonian cycle to metric tour
Given an undirected simple graph with , form the complete graph on the same vertices. Give cost one to an original edge and cost two to a nonedge. The triangle inequality holds: every cost is at most two, while a route through a distinct intermediate vertex has two edges each costing at least one.
Proof
(Costs one and two preserve the answer)
If has a Hamiltonian cycle, that cycle has tour cost . Conversely, every tour has exactly edges, each of cost at least one. A tour of cost at most must use only cost-one edges, so it is a Hamiltonian cycle of . The threshold therefore preserves both answers. A proposed tour and its sum are polynomially checkable, giving NP-completeness of the metric decision problem using the preceding prerequisite and reduction.
The costs are metric even for disconnected input graphs. In that case the complete tour instance still exists; expensive edges connect vertices that were not adjacent in the original graph. These edges make a tour possible but push its cost above when no all-original-edge cycle exists.
A gap for arbitrary tour costs
Proof
(A constant-factor approximation would decide Hamiltonian cycle)
Fix a rational constant . Instead assign cost one to original edges and cost to nonedges. If a Hamiltonian cycle exists, the optimum is exactly . If not, every tour uses a cost- edge and has cost at least .
Suppose a polynomial-time algorithm always returns a tour of cost at most times optimum on these nonnegative instances. Run it and compare the returned integer cost with . In a yes instance the output cost is at most ; in a no instance every feasible output costs more than . This decides undirected Hamiltonian cycle in polynomial time. The integer has polynomial encoding length for fixed rational , and the graph is complete, so the transformation is polynomial.
Counterexample mode
The gap construction is not a metric instance
Claim: the instances built with the large cost are metric, so the gap would also rule out constant-factor approximation for metric tours. Test it on the path with . Then , so and . But , so the triangle inequality fails. The same failure occurs whenever two nonadjacent vertices have a common neighbor, for every . The gap argument therefore applies only to arbitrary nonnegative costs. The cost-one-and-two instances are metric, but their no-instances cost only at least .
The conclusion is conditional: unless , there is no polynomial-time fixed-constant approximation for arbitrary symmetric nonnegative tour costs. This is consistent with positive approximation guarantees for metric tours, whose shortcutting proof uses the triangle inequality.
Worked examples
Worked example 4.5.5
(Splitting a directed cycle)
For the directed cycle , split into . The new edges include , and , giving the Hamiltonian path . Joining its endpoints back into recovers the original cycle.
Worked example 4.5.6
(A two-vertex directed cycle)
For vertices with both directed edges and , the undirected gadget construction gives the six-cycle . The opposite directed edges become two different external edges, and the constructed undirected graph remains simple.
Worked example 4.5.7
(Metric costs on a path)
Let the input graph be the three-vertex path . Its complete cost graph assigns one to and two to . The only undirected tour has cost four, larger than the threshold three, matching the absence of a Hamiltonian cycle in the path graph. The triangle inequality holds with equality on via .
Worked example 4.5.8
(A yes-instance gap)
For a four-cycle on four vertices, the cost-one cycle has total cost four. Under the large- construction with , , and an algorithm satisfying the stated factor must return a tour costing at most eight on this yes instance. In a no instance of the same size every tour would cost at least twelve.
Common mistakes
Common mistake
(Reading a reduction in the wrong direction)
The direction of a reduction matters. A polynomial reduction from problem to problem turns a solver for into a solver for ; it does not by itself turn a solver for into one for . Each proof above supplies both witness transformations so the yes/no equivalence is explicit.
Common mistake
(A threshold that does not separate the cases)
A decision threshold must separate the two cases strictly. For the metric construction, every tour has edges and cost at least , so threshold works exactly. For the approximation gap, choosing a large number without comparing it to is insufficient. The chosen makes the no-instance lower bound strictly greater than the maximum permitted yes-instance output.
Common mistake
(Counting the closing vertex twice)
A cycle certificate lists vertices in cyclic order and can be checked against the relevant edge or cost representation. It need not list the start vertex twice as a distinct vertex; the final edge back to the first is checked separately. This avoids confusing a repeated closing notation with visiting a vertex twice.
Scope of the reductions
The undirected gadget proof relies on a middle vertex having exactly two incident edges. A Hamiltonian cycle must use both, which prevents entering and leaving the gadget through the same endpoint. The external-edge pattern then synchronizes gadget orientations around the entire tour. Merely drawing three vertices per directed vertex without proving these two facts would not rule out a spurious undirected cycle.
Margin Note
Test a gadget by degrees first
Before trusting a gadget, list what a Hamiltonian cycle is forced to do at each of its vertices, starting with those of degree two. Only after the forced edges are fixed should you ask what the remaining choices mean in the original graph.
The metric reduction uses only costs one and two, so its binary encoding is especially small. Yet this does not yield a constant-factor hardness gap: a no-instance tour can cost only one more than , and the ratio approaches one. It proves exact decision hardness. The arbitrary-cost reduction creates a larger gap precisely by allowing costs that need not satisfy the triangle inequality.
This chapter uses directed Hamiltonian-cycle NP-completeness as a prerequisite. Its proofs establish the downstream reductions and membership certificates, not the original reduction from SAT. The exponential subset dynamic program for Hamiltonian paths in a companion unit remains a valid exact algorithm; NP-completeness rules out a polynomial algorithm only under the usual complexity assumption.
Summary
Split a designated directed vertex into forced path endpoints, or replace every directed vertex with a three-vertex undirected gadget. Cost-one original edges and cost-two nonedges yield a metric tour decision reduction. A larger nonmetric gap gives a conditional constant-factor inapproximability consequence, with the triangle inequality limitation made explicit.
Exercises
Quick check
(In the directed-to-path transformation, why must every Hamiltonian path begin at and end at ?)
Look at which edges enter and which leave .
Solution · Answer
No edge enters , so it cannot occur after another path vertex; no edge leaves , so it cannot occur before another vertex. A Hamiltonian path contains both.
Quick check
(Why must both edges incident to appear in any Hamiltonian cycle of the undirected gadget graph?)
Count the neighbors of .
Solution · Answer
The middle vertex has exactly those two neighbors, and a cycle uses two distinct incident edges at each of its vertices.
Quick check
(For a graph on five vertices without a Hamiltonian cycle, what lower bound holds for every tour in the cost-one/cost-two construction?)
A tour has exactly five edges.
Solution · Answer
Every tour has five edges. Without an original Hamiltonian cycle, at least one of those edges costs two and the others cost at least one, so every tour costs at least six. The exact optimum can be larger.
Quick check
(For and , compute and the no-instance lower bound in the large-gap construction.)
Use and count the other edges of a tour.
Solution · Answer
. Any no-instance tour uses an expensive edge and two other edges of cost at least one, so it costs at least , which is greater than .