8
$\begingroup$

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...

Update - Is the problem of iterating Hamiltonian path/circuits known to be NP-complete for the N-cube?

Improve this question
$\endgroup$
6
  • 1
    $\begingroup$ How do you cast "iterating Hamiltonian circuits" as a decision problem? I'd expect that you can list all the Hamiltonian circuits in the n-cube in time polynomial in the length of the output--which is probably about doubly exponential in n... $\endgroup$
    – Reid Barton
    Commented Oct 22, 2009 at 1:13
  • $\begingroup$ Reid, I have made a mistake - I should have said that the detection of a Hamiltonian circuit on a general grid graph is NP-hard. Can you describe your intuition in more detail for the second part of your statement? $\endgroup$
    – Mensen
    Commented Oct 22, 2009 at 19:26
  • $\begingroup$ On the approximate number of Hamiltonian circuits in an n-cube? Well, a circuit goes through all 2^n vertices and makes one of n choices at each step; it seems like you could get through a large proportion of the vertices before "painting yourself into a corner". $\endgroup$
    – Reid Barton
    Commented Oct 22, 2009 at 19:40
  • $\begingroup$ Here's a quick lower bound for the number of circuits on the complete n-cube: Let M(n) denote the number of perfect matchings on Q_n and H(n) denote the number of Hamiltonian cycles. Fink (2007) showed that every perfect matching can be extended to a cycle. Since every cycle contains exactly two matchings we have M(n)/2 <= H(n). On the other hand, we have M(3)=9 (direct counting) and M(n+1) >= M(n)^2 (Divide Q_{n+1} into two copies of Q_n, take a matching on each). This means H(Q_n) grows at least double exponentially in n, and at least exponentially in the size of the graph. $\endgroup$
    – Kevin P. Costello
    Commented Oct 22, 2009 at 21:24
  • $\begingroup$ It may also be worth noting that in general it seems that when there are Hamiltonian cycles, there tends to be exponentially many. This is true for graphs of minimum degree at least n/2 (a result of Cuckler and Kahn) as well as random 3-regular graphs (Robinson and Wormald) $\endgroup$
    – Kevin P. Costello
    Commented Oct 22, 2009 at 21:29

3 Answers 3

Reset to default
5
$\begingroup$

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.

For instance, this paper proves the graph of a random 5-outregular digraph is Hamiltonian and there is an algorithm that finds a Hamiltonian cycle in polynomial time.

Improve this answer
$\endgroup$
6
  • 1
    $\begingroup$ Showing that a Hamiltonian cycle exists is different than enumerating them. For example, as far as I can tell even the number of Hamiltonian cycles on the Hypercube remains unknown (see sequence A003042 in the OEIS) $\endgroup$
    – Kevin P. Costello
    Commented Oct 21, 2009 at 17:09
  • $\begingroup$ I will leave the question open for a little while longer, but thank you for the interesting paper and your answer! $\endgroup$
    – Mensen
    Commented Oct 21, 2009 at 17:18
  • $\begingroup$ Mensen -- you shouldn't close the question, but simply accept your chosen answer. Closing questions is only for questions which are off-topic, abusive, and otherwise inappropriate. $\endgroup$
    – Kim Morrison
    Commented Oct 21, 2009 at 17:24
  • $\begingroup$ Scott, Jason - Done. =) Sorry, I was confused about how this works. $\endgroup$
    – Mensen
    Commented Oct 21, 2009 at 17:28
  • $\begingroup$ Dear Kevin, I came to the same conclusion as you when I was curious about enumerating tours on the N-cube many years ago. I had a positive experience with my last question, so I thought I'd revisit the issue on the site. $\endgroup$
    – Mensen
    Commented Oct 21, 2009 at 17:35
2
$\begingroup$

I can give a partial answer to the first question:

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?

If the grid graph is "solid," ie., has no holes, then there is a polynomial-time algorithm by Umans and Lenhart (paper here) 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.

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.)

So hole-free grid graphs appear to be one such special case.

Improve this answer
$\endgroup$
1
$\begingroup$

I give a reference for the following part of your question:

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?

In the following paper, the authors give a linear-time algorithm for finding a longest path between any two given vertices in a rectangular grid graph.

F. Keshavarz-Kohjerdi, A. Bagheri, A. Asgharian-Sardroud: A linear-time algorithm for the longest path problem in rectangular grid graphs. Discrete Applied Mathematics 160(3): 210-217 (2012)

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .