New answers tagged hamiltonian-path
3
TSPLIB contains some instances of Hamiltonian Cycle. Haythorpe [1] proposes a set of around a thousand instances which are claimed to be "structurally difficult" (not necessarily large).
Haythorpe, Michael. "FHCP Challenge Set: The first set of structurally difficult instances of the Hamiltonian cycle problem." arXiv preprint arXiv:1902....
1
First the reduction from P2 to P1 is easy cause if you can decide whether there is one cycle you can also decide whether there is at least one cycle. The other way around is more tricky.
Notice that P1 can be solved in polynomial time if we have an oracle for P2 (an oracle for P2 means that we can use a subroutine that solves P2).
algorithm for P1 with input ...
Top 50 recent answers are included
