Editing Hamiltonian path problem (section)

==Complexity==
The problem of finding a Hamiltonian cycle or path is in [[FNP (complexity)|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 graph]]s,<ref>{{Cite web|url=https://cs.stackexchange.com/q/18335 |title=Proof that the existence of a Hamilton Path in a bipartite graph is NP-complete|website=Computer Science Stack Exchange|access-date=2019-03-18}}</ref>
* undirected [[planar graph]]s of maximum degree three,<ref>{{citation
 | last1 = Garey | first1 = M. R. | author1-link = Michael Garey
 | last2 = Johnson | first2 = D. S. | author2-link = David S. Johnson
 | last3 = Stockmeyer | first3 = L. | author3-link = Larry Stockmeyer
 | contribution = Some simplified NP-complete problems
 | doi = 10.1145/800119.803884
 | pages = 47–63
 | title = Proc. 6th ACM Symposium on Theory of Computing (STOC '74)
 | year = 1974| s2cid = 207693360 }}.</ref> 
* directed planar graphs with indegree and outdegree at most two,<ref>{{citation
 | last = Plesńik | first = J.
 | issue = 4
 | journal = [[Information Processing Letters]]
 | pages = 199–201
 | title = The NP-completeness of the Hamiltonian cycle problem in planar digraphs with degree bound two
 | url = http://www.aya.or.jp/~babalabo/DownLoad/Plesnik%208.4.192-196.pdf
 | volume = 8
 | year = 1979
 | doi = 10.1016/0020-0190(79)90023-1}}.</ref> 
* [[Bridgeless graph|bridgeless]] undirected planar 3-[[regular graph|regular]] [[bipartite graph]]s, 
* 3-connected 3-regular bipartite graphs,<ref>{{citation
 | last1 = Akiyama | first1 = Takanori
 | last2 = Nishizeki | first2 = Takao | author2-link = Takao Nishizeki
 | last3 = Saito | first3 = Nobuji
 | issue = 2
 | journal = Journal of Information Processing
 | mr = 596313
 | pages = 73–76
 | title = NP-completeness of the Hamiltonian cycle problem for bipartite graphs
 | url = 
 | volume = 3
 | year = 1980–1981}}.</ref> 
* subgraphs of the [[Lattice graph#Square grid graph|square grid graph]],<ref>{{citation
 | last1 = Itai | first1 = Alon
 | last2 = Papadimitriou | first2 = Christos
 | last3 = Szwarcfiter | first3 = Jayme
 | issue = 11
 | journal = [[SIAM Journal on Computing]]
 | pages = 676–686
 | title = Hamilton Paths in Grid Graphs
 | doi = 10.1137/0211056
 | volume = 4
 | year = 1982| citeseerx = 10.1.1.383.1078}}.</ref> 
* cubic subgraphs of the square grid graph.<ref>{{citation
 | last = Buro | first = Michael
 | title = Computers and Games
 | contribution = Simple Amazons endgames and their connection to Hamilton circuits in cubic subgrid graphs
 | contribution-url = http://skatgame.net/mburo/ps/amaend.pdf
 | volume = 2063
 | pages = 250–261
 | doi = 10.1007/3-540-45579-5_17| series = Lecture Notes in Computer Science
 | date = 2001
 | isbn = 978-3-540-43080-3
 | citeseerx = 10.1.1.40.9731
 }}.</ref>

However, for some special classes of graphs, the problem can be solved in polynomial time:

* [[k-vertex-connected graph|4-connected]] planar graphs are always Hamiltonian by a result due to [[W. T. Tutte|Tutte]], and the computational task of finding a Hamiltonian cycle in these graphs can be carried out in linear time<ref>{{citation
 | last1 = Chiba| first1 = Norishige
 | last2 = Nishizeki| first2 = Takao
 | title = The Hamiltonian cycle problem is linear-time solvable for 4-connected planar graphs
 | doi = 10.1016/0196-6774(89)90012-6
 | pages = 187–211
 | journal = Journal of Algorithms
 | volume = 10
 | issue = 2
 | year = 1989}}</ref> 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,<ref>{{citation
 | last1 = Schmid| first1 = Andreas
 | last2 = Schmidt| first2 = Jens M.
 | contribution = Computing Tutte Paths
 | title = Proceedings of the 45th International Colloquium on Automata, Languages and Programming (ICALP'18), to appear.
 | year = 2018
}}</ref> 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.<ref>{{citation
 | last = Thomason
 | first = A. G.
 | contribution = Hamiltonian cycles and uniquely edge colourable graphs
 | doi = 10.1016/S0167-5060(08)70511-9
 | mr = 499124
 | pages = [https://archive.org/details/advancesingrapht0000camb/page/259 259–268]
 | series = Annals of Discrete Mathematics
 | title = Advances in Graph Theory (Cambridge Combinatorial Conf., Trinity College, Cambridge, 1977)
 | volume = 3
 | year = 1978
 | isbn = 9780720408430
 | url = https://archive.org/details/advancesingrapht0000camb/page/259
 }}.</ref> However, finding this second cycle does not seem to be an easy computational task. [[Christos Papadimitriou|Papadimitriou]] defined the [[complexity class]] [[PPA (complexity)|PPA]] to encapsulate problems such as this one.<ref>{{citation | last = Papadimitriou| first = Christos H.| author-link = Christos Papadimitriou | doi = 10.1016/S0022-0000(05)80063-7
| issue = 3
| journal = [[Journal of Computer and System Sciences]]
| pages = 498–532
| title = On the complexity of the parity argument and other inefficient proofs of existence
| volume = 48
| year = 1994 | mr = 1279412| citeseerx = 10.1.1.321.7008
}}.</ref>