Special cases for efficient enumeration of Hamiltonian paths on grid graphs? - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-21T09:54:19Z http://mathoverflow.net/feeds/question/1592 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/1592/special-cases-for-efficient-enumeration-of-hamiltonian-paths-on-grid-graphs Special cases for efficient enumeration of Hamiltonian paths on grid graphs? Mensen 2009-10-21T06:43:28Z 2011-09-26T18:48:33Z <p>While the general problem of detecting a Hamiltonian path or cycle on an undirected grid graph is known to be NP-complete, are there interesting special cases where efficient polynomial time algorithms exist for enumerating all such paths/cycles? Perhaps for certain kinds of k-ary n-cube graphs? I hope this question isn't too open-ended...</p> <p>Update - Is the problem of iterating Hamiltonian path/circuits known to be NP-complete for the N-cube? </p> http://mathoverflow.net/questions/1592/special-cases-for-efficient-enumeration-of-hamiltonian-paths-on-grid-graphs/1687#1687 Answer by Jason Dyer for Special cases for efficient enumeration of Hamiltonian paths on grid graphs? Jason Dyer 2009-10-21T17:03:11Z 2009-10-21T17:03:11Z <p>There are certainly special graphs that are always Hamiltonian (if every vertex of a graph of n vertices has degree at least n/2, say) and these have efficient algorithms associated with them.</p> <p>For instance, <a href="http://www.math.cmu.edu/~af1p/Texfiles/5out.pdf" rel="nofollow">this paper</a> proves the graph of a random 5-outregular digraph is Hamiltonian and there is an algorithm that finds a Hamiltonian cycle in polynomial time.</p> http://mathoverflow.net/questions/1592/special-cases-for-efficient-enumeration-of-hamiltonian-paths-on-grid-graphs/76444#76444 Answer by Aaron Sterling for Special cases for efficient enumeration of Hamiltonian paths on grid graphs? Aaron Sterling 2011-09-26T18:48:33Z 2011-09-26T18:48:33Z <p>I can give a partial answer to the first question:</p> <blockquote> <p>While the general problem of detecting a Hamiltonian path or cycle on an undirected grid graph is known to be NP-complete, are there interesting special cases where efficient polynomial time algorithms exist for enumerating all such paths/cycles?</p> </blockquote> <p>If the grid graph is "solid," ie., has no holes, then there is a polynomial-time algorithm by Umans and Lenhart (paper <a href="http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.47.2950" rel="nofollow">here</a>) that will find a Hamiltonian cycle, or reject the graph if no such cycle exists. The algorithm first finds a maximum matching, and then decomposes the graph into "static alternating strips," both of which can be performed efficiently. Production of the Hamiltonian cycle is achieved by changing the matching depending on how the static alternating strips are laid out.</p> <p>While there may be exponentially many different H cycles, it is possible to enumerate them with polynomial delay (meaning only having to wait for a polynomial amount of time before outputting the next one) by changing the order in which one traverses the static alternating strips, and/or changing the underlying matching. (Caveat: the enumeration algorithm may need to be more careful than my handwaving, to ensure only polynomially-many duplicate cycles are outputted before a new one is. It seems, though, that one could simply build different cycles in parallel, and then prioritize the ones that deviate from one another.)</p> <p>So hole-free grid graphs appear to be one such special case.</p>