Question

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:

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

Answer 1

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

1. The paper is written by some of the best people in the field, and published in the best journal in the field.

2. "General" means "arbitrary".