Hamiltonian completion

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 general case (since its solution gives an answer to the NP-complete problem of determining whether a given graph has a Hamiltonian cycle).

Moreover, it belongs to the APX complexity class, i.e., it is unlikely that efficient constant ratio approximation algorithms exist for this problem. [ Q. S. Wu, C. L. Lu, R. C. T. Lee, [http://www.springerlink.com/content/103cnuhn3aknv262/ An Approximate Algorithm for the Weighted Hamiltonian Path Completion Problem on a Tree] , "Lecture Notes in Computer Science", Vol. 1969 (2000) Pages: 156 - 167]

The problem may be solved in polynomial time for certain classes of graphs, including series-parallel graphs [K. Takamizawa, T. Nishizeki, and N. Saito, Linear-Time Computability of Combinatorial Problems on Series-Parallel Graphs, "J. ACM" 29 (1982) 623–641] and their generalizations [N. M. Korneyenko, Combinatorial algorithms on a class of graphs, "Discrete Applied Mathematics, v.54 n.2-3, p.215-217, 1994] , which include outerplanar graphs, as well as for a line graph of a tree [Arundhati Raychaudhuri, [http://portal.acm.org/citation.cfm?id=222481&dl=GUIDE&coll=GUIDE&CFID=16443822&CFTOKEN=97960415 The total interval number of a tree and the Hamiltonian completion number of its line graph] , Information Processing Letters, Volume 56 , Issue 6 (December 1995) 299 - 306 ] [A. Agnetis, P. Detti, C. Meloni, D. Pacciarelli, [http://portal.acm.org/citation.cfm?id=381021 A linear algorithm for the Hamiltonian completion number of the line graph of a tree] , Information Processing Letters, Volume 79 , Issue 1 (May 2001), 17 - 24 ] or a cactus graph. [ Paolo Detti, Carlo Meloni, [http://portal.acm.org/citation.cfm?id=975923&dl=GUIDE&coll=GUIDE&CFID=13226110&CFTOKEN=18722093 A linear algorithm for the Hamiltonian completion number of the line graph of a cactus] ,Discrete Applied Mathematics,Volume 136 , Issue 2-3 (February 2004) 197 - 215]

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. [David Gamarnik, Maxim Sviridenko, [http://www.mit.edu/~gamarnik/Papers/HamCompletionPublished.pdf Hamiltonian completions of sparse random graphs] , Discrete Applied Mathematics 152 (2005) 139 – 158]

References