0
$\begingroup$

This was a question asked on a previous exam:

Bob is looking for a Hamiltonian cycle in a graph with $n$ vertices. His plan is to start with an arbitrary vertex, write down an adjacent vertex, and continue until either he has written $n$ distinct vertices and can return to the start vertex, or is forced to repeat a vertex. He will never write the same string of vertices, and can choose a new starting vertex each time he tries. Approximately how many strings will Bob need to write to prove there is no Hamiltonian cycle?

I know of Dirac's Theorem, but otherwise have no clue how to go about this problem.

$\endgroup$
  • $\begingroup$ Depends on the graph. In extreme cases, one string suffices. $\endgroup$ – Peter Taylor Dec 9 '19 at 11:04
  • $\begingroup$ Did Bob Dylan write the title to this question? :) $\endgroup$ – user856 Dec 9 '19 at 11:47
  • $\begingroup$ @Rahul, it doesn't scan very well. $\endgroup$ – Gerry Myerson Dec 9 '19 at 11:54
0
$\begingroup$

Determining whether a graph $G=(V,E)$ (undirected or directed) contains an Hamilton cycle (or even path) is NP-complete problem. Roughly speaking, it means that in order to solve this problem you'll have to go though every possibility.

Finding an actual Hamilton cycle is not easier than determining if a graph contain one.

Regarding your question, the method you are using is called pruning. Asymptotically speaking, it's worst case (or even average case) run time is ${O}(2^{n})$. Therefore, the answer to your question is ${O}(2^{n})$ strings in the worst case.

This problem is also known as one of the "Millennium Prize Problems "

| cite | improve this answer | |
$\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.