Assume we have an algorithm HC for HAMILTONIAN CIRCUIT. How is it possible to convert the HC algorithm to an algorithm HP for HAMILTONIAN PATH?

Question

My understanding is that I have to use the algorithm for Hamiltonian Circuit to help solve the Hamiltonian Path problem.

My understanding is that we have to perform a reduction from Hamiltonian Path---> Hamiltonian Circuit (since we have an alg for Hamiltonian Circuit the reduction should be from Ham path---> Ham circuit)

But in contrast, the question says CONVERT the Ham Circuit algorithm to an algorithm to an algorithm of HP. Does this imply that the Ham Circuit problem should be reduced to the Ham Path problem?

Any guidance/feedback greatly appreciated.

Answer 1

The wording of the question is a bit unclear. You're supposed to reduce HamiltonianPath to HamiltonianCircuit: in other words, write an algorithm that solves HamiltonianPath by using a subroutine for HamiltonianCircuit.

I assume you're specifically going for a polytime reduction, so you shouldn't do an exponential amount of work in your new program—but there are a few different types of polytime reductions (Karp vs Cook in particular), and I can't get any more specific without knowing which one you're using. In a Karp reduction, for example, you only get to call the HamiltonianCircuit subroutine once, and have to return its output unmodified—all the transformation has to happen before you make the subroutine call. In a Cook reduction you can call it as many times as you want, and transform the outputs however you like before returning.

Answer 2

Given algorithm $HC$ that solves Hamiltonian Cycle, and a graph $G = (V,E)$ in which you must decide whether a Hamiltonian Path exists:

$\bullet$ Define $G'$ as the graph obtained by adding a new vertex $v'$ to $G$ and connecting it to every $v \in V$

$\bullet$ Apply $HC$ on graph $G'$

If and only if $HC$ found a hamiltonian cycle in $G'$, there is a Hamiltonian path in $G$.