Hamiltonian path problem
≈ 5 min read
Names in other languages
No names in other languages are held for this entry yet.
Article bodies are English and are not machine-translated. A name in another language is not a translation of the article.
The Hamiltonian path problem is a topic discussed in the fields of complexity theory and graph theory. It decides if a directed or undirected graph, G, contains a Hamiltonian path, a path that visits every vertex in the graph exactly once. The problem may specify the start and end of the path, in which case the starting vertex s and ending vertex t must be identified.
The Hamiltonian cycle problem is similar to the Hamiltonian path problem, except it asks if a given graph contains a Hamiltonian cycle. This problem may also specify the start of the cycle.
The Hamiltonian cycle problem is a special case of the travelling salesman problem, obtained by setting the distance between two cities to one if they are adjacent and two otherwise, and verifying that the total distance travelled is equal to n. If so, the route is a Hamiltonian cycle. The Hamiltonian path problem and the Hamiltonian cycle problem belong to the class of NP-complete problems, as shown in Michael Garey and David S. Johnson's book Computers and Intractability: A Guide to the Theory of NP-Completeness and Richard Karp's list of 21 NP-complete problems.
The Hamiltonian path problem is a topic discussed in the fields of complexity theory and graph theory. It decides if a directed or undirected graph, G, contains a Hamiltonian path, a path that visits every vertex in the graph exactly once. The problem may specify the start and end of the path, in which case the starting vertex s and ending vertex t must be identified.
The Hamiltonian cycle problem is similar to the Hamiltonian path problem, except it asks if a given graph contains a Hamiltonian cycle. This problem may also specify the start of the cycle.
The Hamiltonian cycle problem is a special case of the travelling salesman problem, obtained by setting the distance between two cities to one if they are adjacent and two otherwise, and verifying that the total distance travelled is equal to n. If so, the route is a Hamiltonian cycle. The Hamiltonian path problem and the Hamiltonian cycle problem belong to the class of NP-complete problems, as shown in Michael Garey and David S. Johnson's book Computers and Intractability: A Guide to the Theory of NP-Completeness and Richard Karp's list of 21 NP-complete problems.
Complexity
The problem of finding a Hamiltonian cycle or path is in FNP; the analogous decision problem is to test whether a Hamiltonian cycle or path exists. The directed and undirected Hamiltonian cycle problems were two of Karp's 21 NP-complete problems.
They remain NP-complete even for special kinds of graphs, such as: bipartite graphs, undirected planar graphs of maximum degree three, directed planar graphs with indegree and outdegree at most two, bridgeless undirected planar 3-regular bipartite graphs, 3-connected 3-regular bipartite graphs, subgraphs of the square grid graph, cubic subgraphs of the square grid graph. However, for some special classes of graphs, the problem can be solved in polynomial time: 4-connected planar graphs are always Hamiltonian by a result due to Tutte, and the computational task of finding a Hamiltonian cycle in these graphs can be carried out in linear time by computing a so-called Tutte path.
Tutte proved this result by showing that every 2-connected planar graph contains a Tutte path. Tutte paths in turn can be computed in quadratic time even for 2-connected planar graphs, which may be used to find Hamiltonian cycles and long cycles in generalizations of planar graphs.
Putting all of these conditions together, it remains open whether 3-connected 3-regular bipartite planar graphs must always contain a Hamiltonian cycle, in which case the problem restricted to those graphs could not be NP-complete; see Barnette's conjecture. In graphs in which all vertices have odd degree, an argument related to the handshaking lemma shows that the number of Hamiltonian cycles through any fixed edge is always even, so if one Hamiltonian cycle is given, then a second one must also exist.
However, finding this second cycle does not seem to be an easy computational task. Papadimitriou defined the complexity class PPA to encapsulate problems such as this one.
Text derived from https://en.wikipedia.org/w/index.php?oldid=1368356858 under CC BY-SA 4.0; modifications have been made.