MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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 ( 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:
  • 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?
share|cite|improve this question
up vote 1 down vote accepted
  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".

share|cite|improve this answer
May I further ask whether it is possible to convert a non grid graph TSP problem into a grid graph one? If so, what are the search terms I should google for to find the relevant research papers.. Thank you. – darryl Apr 29 '12 at 1:46
darryl: I think that the paper you mentioned in fact shows you how to convert a non grid graph TSP into a grid graph one if you read through the details. The paper might be a little difficult for you, but it is highly unlikely an easier source exists. – Alexander Woo Apr 29 '12 at 4:04
@Alexander... my bad. Thanks, though. Indeed it is a difficult paper for me to grasp but since it is proven that such a problem can be converted into another it has thus answered my question. – darryl Apr 29 '12 at 4:23

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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