0
$\begingroup$

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?

$\endgroup$
2
$\begingroup$

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.

$\endgroup$
0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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