1.Previous
3.Next

and Richard Karp's list of 21 NP-complete problems.

Reductions

Reduction from the path problem to the cycle problem

The problems of finding a Hamiltonian path and a Hamiltonian cycle can be related as follows:

* In one direction, the Hamiltonian path problem for graph G can be related to the Hamiltonian cycle problem in a graph H obtained from G by adding a new universal vertex

1.Previous
3.Next