Hamiltonian completion

Short description: NP-hard problem to find the minimal number of edges to add to a graph to make it Hamiltonian

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 generalizations,^[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

↑ Q. S. Wu, C. L. Lu, R. C. T. Lee, An Approximate Algorithm for the Weighted Hamiltonian Path Completion Problem on a Tree, Lecture Notes in Computer Science, Vol. 1969 (2000) Pages: 156 - 167
↑ 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 .
↑ N. M. Korneyenko, Combinatorial algorithms on a class of graphs, Discrete Applied Mathematics, v.54 n.2-3, p.215-217, 1994
↑ Arundhati Raychaudhuri, 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, 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
↑ Paolo Detti, Carlo Meloni, 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
↑ David Gamarnik, Maxim Sviridenko, Hamiltonian completions of sparse random graphs, Discrete Applied Mathematics 152 (2005) 139 – 158

0.00

(0 votes)

Original source: https://en.wikipedia.org/wiki/Hamiltonian completion. Read more

[1] Q. S. Wu, C. L. Lu, R. C. T. Lee, An Approximate Algorithm for the Weighted Hamiltonian Path Completion Problem on a Tree, Lecture Notes in Computer Science, Vol. 1969 (2000) Pages: 156 - 167

[2] 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 .

[3] N. M. Korneyenko, Combinatorial algorithms on a class of graphs, Discrete Applied Mathematics, v.54 n.2-3, p.215-217, 1994

[4] Arundhati Raychaudhuri, 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

[5] A. Agnetis, P. Detti, C. Meloni, D. Pacciarelli, 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

[6] Paolo Detti, Carlo Meloni, 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

[7] David Gamarnik, Maxim Sviridenko, Hamiltonian completions of sparse random graphs, Discrete Applied Mathematics 152 (2005) 139 – 158

[1]

[2]

[3]

[4]

[5]

[6]

[7]