Why can the Euler path be realized in linear time, but not in Hamiltonian time?

Question

I found out that although it seems that the Euler trajectory can be solved in linear time, while the problem of Hamiltonian paths is NP-complete. I wonder what is the reason for this difference? I don’t know much about graph theory, so I probably won’t understand the rigorous proof, but some jargons should be fine.

Answer 1

In principle, the Euler problem can be solved with the help of dynamic programming, and the Hamilton problem cannot.

This means that if you have a subset of your graph and find the right circular path through it, you can combine this partial solution with other partial solutions and find a globally valid path. This is not so for the optimal path: even after you find the optimal path through a small part of the graph, it may not be part of the global optimal path (and in fact this is usually not the case). 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 the divide and win correctly.

Answer 2

If we take the case of an undirected graph, there is an Eulerian path if the graph is connected and has only two vertices of odd degree (start and end vertices). This path visits each region exactly once. Thus, the existence of the Euler path depends on the degrees of the vertices, and not on the actual number of vertices.

For the Hamiltonian trajectory, the simple necessary conditions are not known (and, of course, not the polynomial time algorithm). Since the path must hit each vertex exactly once, the “hard” way is to check all permutations of the vertices and see if the path exists.

Answer 3

In fact, the restriction of the Hamiltonian path - you should visit the edge only once. But with the Euler, you can visit the same peak, and sometimes the same edge with the opposite direction. In most cases, however, you can create a new vertex, but it is just possible to add an edge.

Bellman, R. (1962), "Dynamic Programming of the Traveling Salesman Problem," ACM 9: 61-63, doi: 10.1145 / 321105.321111.

If you just check this article, there is a dynamic software implementation of charts (of course, not for all types of charts). There are also some implementations of HMM,

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

A good part of the Euler path; you can get subgraphs (both branches and related), and then get the full cycle-graph. In truth, eulerism is mainly for local solutions.

Hope this helps.