5
$\begingroup$

I'm toying around with graph properties and I want to make some effort to check whether a given graph is Hamiltonian. I understand that the general problem is NP-complete, but I'm looking for simple checks that are easy to implement and computationally inexpensive to get some indication.

So I've implemented Dirac's and Ore's theorems to check the sufficient conditions for whether a graph is Hamiltonian (in my implementation Dirac's is a cheap check before I run Ore's). Digging around I found that the Bondy-Chvátal theorem generalizes both and is thus more powerful, but it seems to be less useful for algorithmic purposes.

If I understand it correctly, the theorem states that a graph is Hamiltonian if and only if its closure is Hamiltonian. The only constructive application of this however seems to me to verify that the closure of a graph is a complete graph, which is the case if (and only if?) the graph meets Ore's condition anyway, which is easier to implement efficiently.

I'm wondering though, might there be some other algorithmic application I may have missed, or is Bondy-Chvátal indeed impractical in my scenario (and more of theoretical use in general)?

$\endgroup$
2
$\begingroup$

Other way than Bondy-Chvátal theorem is brute force search. However brute force search isn't an efficient way of solving this problem - there can be an exponential number of possibilities to test.

You won't have to test so many possibilities, if you will try following algorithm:

http://arxiv.org/pdf/1405.6347.pdf

The main principle of algorithm is "to think over" which paths(possibilities) should be checked than check many wrong paths.

Algorithm can remove unnecessary edges from graph and test when Hamiltonian cycle can't exist in graph.

Algorithms implementation:

http://findinghamiltoniancycle.codeplex.com/

$\endgroup$
  • 4
    $\begingroup$ Welcome! We're looking for more detailed answers than this, which is just a couple of links. Obviously, we're not asking you to include the whole paper in your answer but you should at least give a high-level description of what's in it and how you feel it answers the question. $\endgroup$ – David Richerby Nov 19 '15 at 22:28

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.