2
$\begingroup$

How can it be proved that if there's an algorithm which in polynomial time determines whether a graph has a Hamiltonian cycle then there's an algorithm which can find such Hamiltonian cycle in polynomial time as well?

Note: there's no need to devise the actual algorithm I just need to prove that one causes the other to hold.

I thought that perhaps the algorithm A which just determines whether the graph contains a Hamiltonian cycle has to perform the same amount of work as the algorithm B which has to find the actual cycle because each node has to be visited.

But I'm not sure how to actually prove this.

$\endgroup$
  • $\begingroup$ You need to come up with an algorithm that can find a Hamiltonian cycle in polynomial time, given a polynomial time algorithm to determine whether any graph has an Hamiltonian path. Hint: What happens when we remove a vertex from the graph? $\endgroup$ – Discrete lizard Jan 25 '18 at 14:44
  • $\begingroup$ @Discretelizard we may have several connected components $\endgroup$ – Yos Jan 25 '18 at 14:47
  • 1
    $\begingroup$ @Yos No in Hamiltonian path or cycle is defined for connected graph only $\endgroup$ – Complexity Jan 25 '18 at 15:22
6
$\begingroup$

Input: A graph G = (V, E) for which the checker algorithm is true.

if you remove an edge $e\in E$ from The graph and run the algorithm then if it returns false the removed edge must be part of every hamiltonian cycle in the graph.

If the result is true then we can remove the edge and remove another edge we haven't checked yet and run the algorithm again.

Eventually the graph will only contain a hamiltonian cycle. in O(e) applications of the algorithm.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.