Finding a second Hamilton cycle in a cubic graph

Status open high confidence

The problem of finding a second Hamilton cycle in a cubic graph (given one Hamilton cycle) in polynomial time remains open as of 2026. The best known exact algorithm, due to Deligkas, Mertzios, Spirakis, and Zamaraev (2020), runs in time O(n · 2^((0.3−ε)n)) with polynomial space, which is an exponential-time improvement over prior work but far from polynomial. The same paper also gives a linear-time approximation algorithm that finds a second cycle of length at least n − 4α(√n + 2α) + 8, but this does not answer the membership-in-P question. No polynomial-time algorithm is known, and the problem has not been placed in P.

Cited literature (1)

• partial Exact and Approximate Algorithms for Computing a Second Hamiltonian Cycle (2020)
  Argyrios Deligkas, George B. Mertzios, Paul G. Spirakis, Viktor Zamaraev · arXiv preprint · arXiv:2004.06036

  Provides an exact algorithm in time O(n · 2^((0.3−ε)n)) with polynomial space for finding a second Hamilton cycle in cubic graphs, and a linear-time approximation algorithm guaranteeing a second cycle of length at least n − 4α(√n+2α)+8; the problem in P remains open.

Reviewer notes. The Wikipedia article on the Hamiltonian path problem notes that Papadimitriou introduced the class PPA precisely for problems of this type (finding a second object guaranteed by a parity argument such as handshaking/Smith's theorem); however, the exact complexity-class placement of the cubic-graph case (in P, PPAD, or PPA-complete) has not been resolved in the papers found. The related OPG records concern existence questions (are there uniquely Hamiltonian 4-connected or regular graphs?) rather than the algorithmic question here. The Deligkas et al. 2020 paper is the most recent primary source found addressing the exact statement.

Auto-reviewed 2026-09-10 with claude-sonnet-4-6 (web search enabled).