The Hamiltonian Cycle Decision Problem

The Decision Problem and Its Certificates

A Hamiltonian cycle is a cycle that visits every vertex of a graph exactly once before returning to its start. The decision problem asks whether such a cycle exists. The central complexity distinction is between finding a cycle and checking a proposed one: a proposed ordering of the vertices can be checked efficiently, even though no polynomial-time method for finding a cycle is known in general.

Throughout this tutorial, a directed graph is finite and has no loops or multiple directed edges. For a directed edge from \(u\) to \(v\), we write \((u,v)\). A directed cycle of length \(k\ge 2\) is a sequence \(v_1,\ldots,v_k\) of distinct vertices such that \((v_i,v_{i+1})\) is an edge for \(1\le i<k\), and \((v_k,v_1)\) is an edge. The Hamiltonian-cycle decision problem considered here has inputs with \(n=|V|\ge 3\). The empty graph and graphs with fewer than three vertices are rejected; thus there is no empty-cycle exception.

For a graph on \(n\) vertices, a certificate can be written as a list \(v_1,\ldots,v_n\). A verifier checks that the list contains each vertex exactly once and then checks the \(n\) required directed edges \((v_1,v_2),\ldots,(v_{n-1},v_n),(v_n,v_1)\). It accepts precisely when all these checks succeed. This list has length polynomial in the input size, and the checks can be performed in polynomial time. In particular, if the graph is encoded by an adjacency matrix, each edge lookup takes constant time and the list can be checked in polynomial time. If it is encoded by an edge list, sorting or marking the vertices and edges also gives a polynomial-time check.

This proves that directed Hamiltonian Cycle belongs to NP: every YES instance has a polynomial-size certificate accepted by a polynomial-time verifier, and no NO instance has an accepted certificate. The statement is about verification, not about an algorithm that efficiently finds a certificate whenever one exists.

Polynomial-Time Verification

Proof. Let the proposed list be \(v_1,\ldots,v_n\). Check first that each entry belongs to \(V\), that no vertex occurs twice, and that every vertex occurs. These checks can be done by marking vertices as they are read and then examining the marks. Reject if any check fails. If all pass, the entries are a permutation of \(V\). Check the \(n\) ordered pairs \((v_i,v_{i+1})\) for \(1\le i<n\), together with \((v_n,v_1)\), against the edge set. Accept if and only if all are edges. By the definition of a directed Hamiltonian cycle, acceptance means exactly that the list gives such a cycle. The list has \(n\) entries and there are \(n\) edge checks; each check takes polynomial time under either a standard adjacency-matrix or edge-list encoding. Thus the verification time is polynomial in the input size. \(\square\)

The proposition justifies the certificate claim in both directions. If a Hamiltonian cycle exists, listing its vertices in cycle order gives a certificate that passes. Conversely, if a certificate passes, its entries are all distinct and cover \(V\), and the required directed edges close the list into a cycle. So the verifier cannot accept a list that fails to represent a Hamiltonian cycle.

NP-Hardness and the 3-SAT Reduction

Membership in NP does not show that the problem is difficult: it only shows that proposed YES certificates are efficiently checkable. To establish NP-hardness, one gives a polynomial-time many-one reduction from a problem already known to be NP-hard. For a reduction from 3-SAT, the required output is a directed graph \(G_\varphi\) built from a 3-SAT formula \(\varphi\), such that \(\varphi\) is satisfiable exactly when \(G_\varphi\) has a Hamiltonian cycle. The construction must itself take polynomial time.

That citation supplies the NP-hardness claim, but it is important to know what the cited reduction must establish. A variable gadget must encode the two possible truth values for a variable in the traversal choices of a Hamiltonian cycle. A clause gadget must ensure that the cycle can cover its clause-related vertices only when at least one literal in that clause is made true by the chosen variable traversals. The connecting edges must also join the gadgets so that all local choices fit into one global cycle.

Correctness requires two separate implications. In the forward direction, start with a satisfying assignment and construct a Hamiltonian cycle: specify how each variable gadget is traversed, and for each clause specify a true literal that permits the clause gadget to be covered. In the reverse direction, start with an arbitrary Hamiltonian cycle in the constructed graph. Prove that its traversal through each variable gadget defines a consistent truth value, and then prove that the way it covers each clause gadget identifies a satisfied literal. A construction that proves only that satisfying assignments produce cycles does not rule out cycles arising from unsatisfying formulas.

For a self-contained gadget proof, the vertices and edges of every gadget and connector must be explicitly specified. It is not enough to say that the allowed traversals have a desired form: one must derive that form from the actual edges and from the requirement that every vertex have exactly one predecessor and one successor in the cycle. One must also rule out unintended ways for a cycle to enter, leave, or mix the gadgets. The cited NP-hardness theorem guarantees that such a polynomial construction and proof exist; the preceding list explains the obligations a presentation of that proof would need to meet.

Since 3-SAT is NP-hard, the cited polynomial reduction implies that a polynomial-time algorithm for directed Hamiltonian Cycle would yield a polynomial-time algorithm for 3-SAT. The reduction direction matters: the constructed graph is obtained from the formula, and satisfiability must be equivalent to the existence of a Hamiltonian cycle. Together with the certificate verifier, this gives the standard conclusion that directed Hamiltonian Cycle is NP-complete.

Common Pitfalls and Scope

Confusing verification with construction. The verifier checks a proposed cycle; it does not find one. A certificate may be easy to check even when finding a certificate is computationally difficult. The NP-completeness result concerns this difference.

Leaving small inputs ambiguous. The definition here rejects inputs with fewer than three vertices, including the empty graph. The certificate verifier is specified for \(n\ge3\); a complete decision algorithm first checks the input size and rejects otherwise. This avoids accidentally accepting an empty list as a cycle.

Proving only one direction of a reduction. Showing that every satisfying assignment gives a Hamiltonian cycle does not prove NP-hardness by itself. One must also show that every Hamiltonian cycle in the constructed graph yields a satisfying assignment. Both directions depend on the exact gadget edges and on excluding unintended traversals.

Ignoring the encoding and construction time. A reduction is polynomial only if the output graph can be generated in polynomial time and has polynomial size in the formula length. A correct logical correspondence alone is not sufficient if the construction uses exponentially many vertices or edges.