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 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
- ↑ 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, Algorithms and Computation, 11th International Conference, ISAAC 2000, Taipei, Taiwan, December 18–20, 2000, Proceedings, Lecture Notes in Computer Science, 1969, Springer, pp. 156–167, doi:10.1007/3-540-40996-3_14, ISBN 978-3-540-41255-7
- ↑ Takamizawa, K. (1982), "Linear-time computability of combinatorial problems on series–parallel graphs", Journal of the ACM 29 (3): 623–641, doi:10.1145/322326.322328.
- ↑ 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
- ↑ 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
- ↑ 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
- ↑ 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
- ↑ Gamarnik, David; Sviridenko, Maxim (2005), "Hamiltonian completions of sparse random graphs", Discrete Applied Mathematics 152 (1–3): 139–158, doi:10.1016/j.dam.2005.05.001, https://www.mit.edu/~gamarnik/Papers/HamCompletionPublished.pdf
 |  |
