Hamiltonian Path

Input

Graph $G = (V, E)$.

Question

Does $G$ contain a Hamiltonian path?

Classes

• NP-complete

Comments

Remains NP-complete under restrictions (1) and (2) for Hamiltonian Circuit and is polynomially solvable under the same restrictions as Hamiltonian Circuit. Corresponding [problem:directed-hamiltonian-path] problem is also NP-complete, and the comments for Directed Hamiltonian Circuit apply to it as well. The variants in which either the starting point or the ending point or both are specified in the instance are also NP-complete. [problem:directed-hamiltonian-path] can be solved in polynomial time for acyclic digraphs, e.g., see (Lawler, 1976).

Proofs

NP-complete

Transformation from Vertex Cover.

Reducible from

• Vertex Cover

Reducible to

• Degree Constrained Spanning Tree

References

• Lawler, E. L. (1976). Combinatorial optimization: networks and matroids. Holt, Rinehart.