Hamiltonian completion
{{Short description|Adding edges to make a graph Hamiltonian}}
File:Hamiltonian completion.svg (marked by dotted blue lines).]]
The Hamiltonian completion problem is to find the minimal number of edges to add to a graph to make it Hamiltonian.
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.{{citation
| last1 = Wu | first1 = Q. S.
| last2 = Lu | first2 = Chin Lung
| last3 = Lee | first3 = Richard C. T.
| editor1-last = Lee | editor1-first = D. T.
| editor2-last = Teng | editor2-first = Shang-Hua
| contribution = An approximate algorithm for the weighted Hamiltonian path completion problem on a tree
| doi = 10.1007/3-540-40996-3_14
| pages = 156–167
| publisher = Springer
| series = Lecture Notes in Computer Science
| title = Algorithms and Computation, 11th International Conference, ISAAC 2000, Taipei, Taiwan, December 18–20, 2000, Proceedings
| volume = 1969
| year = 2000| isbn = 978-3-540-41255-7
}}
The problem may be solved in polynomial time for certain classes of graphs, including series–parallel graphs{{citation
| last1 = Takamizawa | first1 = K.
| last2 = Nishizeki | first2 = T. | author2-link = Takao Nishizeki
| last3 = Saito | first3 = N.
| doi = 10.1145/322326.322328
| issue = 3
| journal = Journal of the ACM
| pages = 623–641
| title = Linear-time computability of combinatorial problems on series–parallel graphs
| volume = 29
| year = 1982| s2cid = 16082154
| doi-access = free
}}. and their subgraphs,{{citation
| last = Korneyenko | first = N. M.
| doi = 10.1016/0166-218X(94)90022-1
| issue = 2–3
| journal = Discrete Applied Mathematics
| mr = 1300246
| pages = 215–217
| title = Combinatorial algorithms on a class of graphs
| volume = 54
| year = 1994| doi-access = free
}} which include outerplanar graphs, as well as for a line graph of a tree{{citation
| last = Raychaudhuri | first = Arundhati
| doi = 10.1016/0020-0190(95)00163-8
| issue = 6
| journal = Information Processing Letters
| mr = 1366337
| pages = 299–306
| title = The total interval number of a tree and the Hamiltonian completion number of its line graph
| volume = 56
| year = 1995}}{{citation
| last1 = Agnetis | first1 = A.
| last2 = Detti | first2 = P.
| last3 = Meloni | first3 = C.
| last4 = Pacciarelli | first4 = D.
| doi = 10.1016/S0020-0190(00)00164-2
| issue = 1
| journal = Information Processing Letters
| mr = 1832044
| pages = 17–24
| title = A linear algorithm for the Hamiltonian completion number of the line graph of a tree
| volume = 79
| year = 2001}}
or a cactus graph.{{citation
| last1 = Detti | first1 = Paolo
| last2 = Meloni | first2 = Carlo
| doi = 10.1016/S0166-218X(03)00441-4
| issue = 2–3
| journal = Discrete Applied Mathematics
| mr = 2045212
| pages = 197–215
| title = A linear algorithm for the Hamiltonian completion number of the line graph of a cactus
| volume = 136
| year = 2004}}
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.{{citation
| last1 = Gamarnik | first1 = David
| last2 = Sviridenko | first2 = Maxim
| doi = 10.1016/j.dam.2005.05.001
| issue = 1–3
| journal = Discrete Applied Mathematics
| mr = 2174199
| pages = 139–158
| title = Hamiltonian completions of sparse random graphs
| url = https://www.mit.edu/~gamarnik/Papers/HamCompletionPublished.pdf
| volume = 152
| year = 2005}}