Is it intuitive to see that finding a Hamiltonian path is not in P while finding Euler path is?

Problem Detail: 

I am not sure I see it. From what I understand, edges and vertices are complements for each other and it is quite surprising that this difference exists.

Is there a good / quick / easy way to see that in fact finding a Hamiltonian path should be much harder than finding a Euler path?

Asked By : Lazer

Answered By : A.Schulz

Maybe the following perspective helps:

When you are trying to construct a Eulerian path, you can proceed almost greedily. You just start the path somewhere and the try to walk as long as possible. If you detect a circle, you will delete its edges (but record that this circle was constructed). By this you decompose the graph in circles, which can be easily combined to an Eulerian tour. The point is, none of your decision "how to walk across the graph" can actually be wrong. You will always succeed and never get stuck.

The situation with Hamiltonian paths is different. Again, you might want to construct a path by walking along edges of the graph. But this time you can really make bad decisions. This means you cannot continue the path, but not all vertices have been visited. What you can do is back-track. That means you revert some of your old decisions and continue along a different path. Essentially all algorithms that are known for the general problem rely on some way or the other on back-tracking, or trying out a large set of solutions. This, however, is characteristic for NP-complete problems.

So (simplified) bottom-line: Eulerian path requires no back-tracking, but Hamiltonian path does.

(Notice that it might be that P=NP and in this case a clever Hamiltonian path algorithm would exist.)

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/2837