1
$\begingroup$

If we have an algorithm that in polynomial time says if a graph G has an hamiltonian cycle, can we have an algorithm that in polynomial time find an hamiltonian cycle?

My attempt is to delete an edge of graph G and have G', after run the algorithm on G' to know if it has an hamiltonian cycle if not it means that the edge is in some hamiltonian cycle. Now I don't know how to go on.

Improve this question
$\endgroup$
1
  • $\begingroup$ Perhaps it would be worthwhile to spend some more time on this problem. For instance, you might start by thinking about what you could do once you know that the edge is or isn't in a Hamiltonian cycle, then checking to see if your strategy works or not, and if not, why it fails. $\endgroup$
    – D.W. ♦
    Dec 1, 2019 at 18:11

1 Answer 1

Reset to default
1
$\begingroup$

Let $P$ be an arbitrary simple path in the graph. If $P$ appears in a Hamiltonian cycle of the graph, you can remove all the vertices of $p$ except the first and the last vertex, connect these two vertices with an edge and the resulting graph must be Hamiltonian.

Keeping this in mind, we can build the Hamiltonian cycle step by step starting with path of length one, since you already described how to build such a path. Then we can extend a path of length $i$ to a path of length $i+1$ using the trick above, where we try all neighbors of the last vertex in the path as a next vertex and we apply the trick above to check if a Hamiltonian cycle exists where the new path is a part of the cycle. Note that we call the black-box at most $m := |E|$ times. Once we reach a path of length $n-3$ it is easy to complete the path into a Hamiltonian cycle in linear time.

Improve this answer
$\endgroup$
3
  • $\begingroup$ Thank you, It seems like a depth-first-search, dont' you think it? I don't understand why is necessary your first observation ragarding the P path. $\endgroup$
    – asv
    Dec 1, 2019 at 23:10
  • 1
    $\begingroup$ I was just trying to show to expanding step separately. It is more of an iterative method than a dfs since you will never have to backtrack (you always choose a next vertex where you are sure that it will work). $\endgroup$
    – Narek Bojikian
    Dec 2, 2019 at 2:10
  • 1
    $\begingroup$ Ok, thank you very much $\endgroup$
    – asv
    Dec 2, 2019 at 12:14

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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