Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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|improve this question

1 Answer 1

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|improve this answer

Your Answer

 
discard

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.