1
$\begingroup$
  1. What algorithm would you use to count all the Hamiltionian paths in a $n \times m$ grid graph ($n$ and $m<10$) from a given starting vertex to an ending one?

  2. How can you determine if this grid graph has holes?

Thanks in advance.

$\endgroup$
7
  • 1
    $\begingroup$ On such a small graph, even the most naive algorithm would be fast, so I wouldn't bother with efficiency (unless you're trying to do this by hand!) $\endgroup$ Aug 22, 2010 at 13:18
  • $\begingroup$ @Thierry Zell: Is that true? Setting n=m=9 yields a graph with 81 vertices and maximum degree 4, and I am not so sure that naive algorithms will be fast for graphs of this size. $\endgroup$ Aug 22, 2010 at 16:53
  • $\begingroup$ Then answer is sometimes zero. Color the vertices like a chessboard. If there are an odd number of vertices you can't start and end on a white vertex. $\endgroup$
    – Emil
    Aug 22, 2010 at 18:13
  • 3
    $\begingroup$ Alon Itai, Christos H. Papadimitriou, and Jayme Luiz Szwarcfiter, "Hamilton Paths in Grid Graphs," SIAM J. Comput. Volume 11, Issue 4, pp. 676-686: "...we give necessary and sufficient conditions for the graph to have a Hamilton path between these two nodes." $\endgroup$ Aug 22, 2010 at 19:24
  • $\begingroup$ I think I remember having been told the Hamiltonian Path problem was NP-Hard on subgraphs of grids... If you are interested in this, I know who to ask for references. Your question is about computing the number of them, so it's not an answer but I thought I may mention it, just in case ... $\endgroup$ Aug 22, 2010 at 23:59

1 Answer 1

4
$\begingroup$

Here is Mathematica code that finds all the Hamiltonian paths between opposite corners of a $5 \times 5$ grid graph:

<< Combinatorica`;
n = 5;
G = GridGraph[n, n];
(* Add dangling edges to corners to force start/end vertices *)
Gplus = AddVertex[G, {0, 0}];
Gplus = AddVertex[Gplus, {n + 1, n + 1}];
Gplus = AddEdge[Gplus, {1, n^2 + 1}];
Gplus = AddEdge[Gplus, {n^2, n^2 + 2}];
ShowGraph[Gplus]
H = HamiltonianPath[Gplus, All];
Print["Number of paths=", Length[H]];
Print["Paths=", H];
Number of paths=208
Paths={{26,1,2,3,4,5,10,9,8,7,6,11,12,13,14,15,20,19,18,17,16,21,22,23,24,25,27}, [etc.]}

GridGraph


Addendum. Setting $n=7$ to compute the comparable number for a $7 \times 7$ grid returns 223,424 Hamiltonian paths between opposite corners. [5 hrs computation time on a 2.5GHz laptop.] The first one returned is:

{50, 1, 2, 3, 4, 5, 6, 7, 14, 13, 12, 11, 10, 9, 8, 15, 16, 17, 18,
19, 20, 21, 28, 27, 26, 25, 24, 23, 22, 29, 30, 31, 32, 33, 34, 35,
42, 41, 40, 39, 38, 37, 36, 43, 44, 45, 46, 47, 48, 49, 51}
$\endgroup$
2
  • 1
    $\begingroup$ Would you by any chance know how the Hamiltonian Path problem is solved in Mathematica ? I found the source of the Combinatorica package [1], and the HamiltonianPath seems to call the HamiltonianCycle function, but I have to admit I do not really understand what is going on in this function. It looks too short to be anything more complicated than a bruteforce enumeration, but I am having a very hard time with their syntax ^^; THanks [1] cs.uiowa.edu/~sriram/Combinatorica/NewCombinatorica.m $\endgroup$ Aug 22, 2010 at 23:57
  • $\begingroup$ @Nathann: Sorry, I don't know offhand, but I suspect Combinatorica follows F. Rubin, "A Search Procedure for Hamilton Paths and Circuits," J. ACM 21, 576-580, 1974. $\endgroup$ Aug 23, 2010 at 0:03

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.