Hamiltonian completion

The Hamiltonian completion problem is to find the minimal number of edges to add to a graph to make it Hamiltonian.

A cycle connecting all points already exists in the top graph (marked by bold edges as opposed to the thin edges which aren't part of the cycle), but edge additions are necessary to make the middle and bottom graphs Hamiltonian (marked by dotted blue lines).

The problem is clearly NP-hard in the general case (since its solution gives an answer to the NP-complete problem of determining whether a given graph has a Hamiltonian cycle). The associated decision problem of determining whether K edges can be added to a given graph to produce a Hamiltonian graph is NP-complete.

Moreover, Hamiltonian completion belongs to the APX complexity class, i.e., it is unlikely that efficient constant ratio approximation algorithms exist for this problem.^[1]

The problem may be solved in polynomial time for certain classes of graphs, including series–parallel graphs^[2] and their subgraphs,^[3] which include outerplanar graphs, as well as for a line graph of a tree^[4][5] or a cactus graph.^[6]

Gamarnik et al. use a linear time algorithm for solving the problem on trees to study the asymptotic number of edges that must be added for sparse random graphs to make them Hamiltonian.^[7]