CODEWITHSUNDEEP
graph-theory
Jingping
Jingping

Reputation: 147

Why Eulerian path can be implemented in linear time, but not Hamiltonian path?

I learned that even though seemingly similar, Eulerian path can be solved in linear time while Hamiltonian path problem is NP-complete. I wonder what is the reason that underlies this difference? I don't know too much graph theory so probably won't understand well a rigorous proof, but some jargons should be fine.

Upvotes: 4

Views: 3571

Answers (3)

teutara
teutara

Reputation: 635

In fact, the limitation of Hamiltonian path is you have to visit an edge only once. But with Eulerian you might visit the same vertex, and sometimes same edge with opposite direction. In most cases however, it is possible to create a new vertex but merely possible add an edge.

Bellman, R. (1962), "Dynamic programming treatment of the travelling salesman problem", Journal of the ACM 9: 61–63, doi:10.1145/321105.321111 .

If you just check that article, there is a dynamic programming implementation of graphs (not for all kinds of graphs of course).. And also there are some HMM implementations as well,

Björklund, Andreas (2010), "Determinant sums for undirected Hamiltonicity", Proc. 51st IEEE Symposium on Foundations of Computer Science (FOCS '10), pp. 173–182, arXiv:1008.0541 , doi:10.1109/FOCS.2010.24.

The good part of eulerian path is; you can get subgraphs (branch and bound alike), and then get the total cycle-graph. Truth to be said, eulerian mostly is for local solutions..

Hope that helps..

Upvotes: 1

Kilian Foth
Kilian Foth

Reputation: 14346

Basically, the Euler problem can be solved with dynamic programming, and the Hamilton problem can't.

This means that if you have a subset of your graph and find a valid circular path through it, you can combined this partial solution with other partial solutions and find a globally valid path. That isn't so for the optimal path: even after you have found the optimal path through a small part of a graph, this may very well not be a part of the globally optimal path (and in fact, it usually isn't). Informally, the optimal path through a large graph depends on the exact values in all other parts of the graph, and therefore no one has ever found a way to use "divide and conquer" correctly on the problem.

Upvotes: 6

Prakash Murali
Prakash Murali

Reputation: 106

If we take the case of an undirected graph, a Eulerian path exists if the graph is connected and has only two vertices of odd degree (start and end vertices). This path visits every edge exactly once. So, the existence of Eulerian path is dependent on the vertex degrees and not on the actual number of vertices.

For Hamiltonian path, no simple necessary conditions are known (and of course no polynomial time algorithm). Since the path has to hit every vertex exactly once, the "hard" way is to check all permutations of vertices and see if the path exists.

Upvotes: 4

Related Questions