[Math] Hamiltonian paths in grid graphs

co.combinatoricsgraph theory

I'm a non-mathematically inclined amateur whom is presently interested in Hamiltonian paths / Traveling Salesman problems.

I would like to request that someone be kind enough to tell me whether my understanding of the following sentence found in this research paper (http://www.cs.technion.ac.il/~itai/publications/Algorithms/Hamilton-paths.pdf) is correct:

"In contrast, the Hamilton path (and circuit) problem for general grid graphs is shown to be NP-complete"

My understanding:

A grid graph is this type of graph: http://mathworld.wolfram.com/images/eps-gif/GridGraph_701.gif
NP-complete means if anyone can solve it, then a non general grid graph can be converted int o a general grid graph and be solved using the same algorithm.
Traveling Salesman Problem is a Hamiltonian path (circuit)

Additional questions:

Is the paper credible?
What does the 'general' in 'general grid graph' mean?

Best Answer

It means that there are some grid graphs for which there is some simple algorithm (or simply an existence/nonexistence proof), but this cannot be done for an arbitrary grid graph.

2.Traveling Salesman is not generally the same problem as hamiltonian path/circuit (usually there are costs involved).

The paper is written by some of the best people in the field, and published in the best journal in the field.
"General" means "arbitrary".

Related Solutions

[Math] Special cases for efficient enumeration of Hamiltonian paths on grid graphs

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.

[Math] Efficient way to count Hamiltonian paths in a grid graph for a given pair of vertices

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}

Best Answer

Related Solutions

[Math] Special cases for efficient enumeration of Hamiltonian paths on grid graphs

[Math] Efficient way to count Hamiltonian paths in a grid graph for a given pair of vertices

Related Question