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

Correct me if I'm wrong but can't the nearest neighbor algorithm be used to find a Hamiltonian Circuit in an arbitrary graph and hence proved P = NP?

share|cite|improve this question
up vote 2 down vote accepted

The nearest neighbor algorithm as I understand it (repeatedly select a neighboring vertex that hasn't been visited yet and travel to that vertex) does not guarantee that you will find a circuit even if one exists. For example consider the graph with vertices A,B,C,D with edges AB, AC, AD, BC and CD (a complete graph on 4 vertices with edge BD removed). Starting at A, you travel to C. You can then travel to either B or D, at which point your only choice is to go back to A. So if you go from A to C, you can't complete the loop and construct a Hamiltonian circuit even though one exists.

share|cite|improve this answer

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.