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.[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]
References
edit- ^ Wu, Q. S.; Lu, Chin Lung; Lee, Richard C. T. (2000), "An approximate algorithm for the weighted Hamiltonian path completion problem on a tree", in Lee, D. T.; Teng, Shang-Hua (eds.), Algorithms and Computation, 11th International Conference, ISAAC 2000, Taipei, Taiwan, December 18–20, 2000, Proceedings, Lecture Notes in Computer Science, vol. 1969, Springer, pp. 156–167, doi:10.1007/3-540-40996-3_14, ISBN 978-3-540-41255-7
- ^ Takamizawa, K.; Nishizeki, T.; Saito, N. (1982), "Linear-time computability of combinatorial problems on series–parallel graphs", Journal of the ACM, 29 (3): 623–641, doi:10.1145/322326.322328, S2CID 16082154.
- ^ Korneyenko, N. M. (1994), "Combinatorial algorithms on a class of graphs", Discrete Applied Mathematics, 54 (2–3): 215–217, doi:10.1016/0166-218X(94)90022-1, MR 1300246
- ^ Raychaudhuri, Arundhati (1995), "The total interval number of a tree and the Hamiltonian completion number of its line graph", Information Processing Letters, 56 (6): 299–306, doi:10.1016/0020-0190(95)00163-8, MR 1366337
- ^ Agnetis, A.; Detti, P.; Meloni, C.; Pacciarelli, D. (2001), "A linear algorithm for the Hamiltonian completion number of the line graph of a tree", Information Processing Letters, 79 (1): 17–24, doi:10.1016/S0020-0190(00)00164-2, MR 1832044
- ^ Detti, Paolo; Meloni, Carlo (2004), "A linear algorithm for the Hamiltonian completion number of the line graph of a cactus", Discrete Applied Mathematics, 136 (2–3): 197–215, doi:10.1016/S0166-218X(03)00441-4, MR 2045212
- ^ Gamarnik, David; Sviridenko, Maxim (2005), "Hamiltonian completions of sparse random graphs" (PDF), Discrete Applied Mathematics, 152 (1–3): 139–158, doi:10.1016/j.dam.2005.05.001, MR 2174199