finding cycles - currently using HUGE array

[tp927]

hi,

perhaps this should be in 'code it better', or perhaps here.

I'm writing a program to find hamiltonian cycles in a graph, which could be very large (18 vertices).

currently, i start at the vertex of least degree, then store all possible hamiltonian (i.e. don't visit a vertex more than once) paths of length 3 in an array, then all of length 4.... continuing up to 18, then check which ones can have their ends joined up to find a cycle.

the thing is, i need to my array to be about 10,000,000 entries long for me to get up to about 10!!!

if the probability of one vertex being joined to another is 0.5, then you'd expect there to be about:

8.5*8*7.5*...*(0.5*(17-n))

paths of length n, right?

so this is only going to get bigger.

I only want to check whether a hamiltonion cycle exists though, not find all of them!

what can i do to make my code more manageable and specific to my problem?

[jemidiah]

I think the expected number of paths of length n is a harder calculation, but yeah it should grow similarly to the factorial function (and similarly to what you wrote, for that matter; I just think there are some correction terms). Any algorithm with a growth rate near that speed is just plain intractable on a computer, so a better algorithm is necessary.

Unfortunately, there's some bad news. From this page (http://en.wikipedia.org/wiki/Hamiltonian_path_problem),

In the mathematical field of graph theory the Hamiltonian path problem and the Hamiltonian cycle problem are problems of determining whether a Hamiltonian path or a Hamiltonian cycle exists in a given graph (whether directed or undirected). Both problems are NP-complete.


From this page (http://en.wikipedia.org/wiki/NP_(complexity)#Why_some_NP_problems_are_hard_to_solve),

...because dedicated research has failed to find a polynomial algorithm for any NP-complete problem, once a problem has been proven to be NP-complete this is widely regarded as a sign that a polynomial algorithm for this problem is unlikely to exist.


That is, your problem is probably intractable. Sorry. There are loads of approximation algorithms, though. There's a very direct translation between the Traveling Salesman Problem (TSP) and the Hamiltonian Cycle problem (set city edge weights to 1). There are approximation algorithms to TSP, since it's very useful. I'd be shocked if you found anything quick and certainly correct, though. (In fact, if you do find an algorithm that's quick as n increases, send me an email and we can share the Turing award.)


Does your problem happen to have additional structure to it? The above is all just for the case of a general graph. For instance, if your graph is always a stick (i.e. you can make it into a series of connected line segments) then the Hamiltonian Cycle problem is trivial.