Hamiltonian completion: Difference between revisions

From Wikipedia, the free encyclopedia
Browse history interactively
← Previous editNext edit →
Content deleted Content added
VisualWikitext
m →‎top: clean up spacing around commas and other punctuation fixes, replaced: , → , (3)
unify ref style
Line 4: Line 4:
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.
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.<ref>Q. S. Wu, C. L. Lu, R. C. T. Lee, [https://doi.org/10.1007%2F3-540-40996-3_14 An Approximate Algorithm for the Weighted Hamiltonian Path Completion Problem on a Tree], ''[[Lecture Notes in Computer Science]]'', Vol. 1969 (2000) Pages: 156 - 167</ref>
Moreover, Hamiltonian completion belongs to the [[APX]] [[complexity class]], i.e., it is unlikely that efficient [[constant ratio approximation]] algorithms exist for this problem.<ref>{{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}}</ref>


The problem may be solved in [[polynomial time]] for certain classes of graphs, including [[series–parallel graph]]s<ref>{{citation
The problem may be solved in [[polynomial time]] for certain classes of graphs, including [[series–parallel graph]]s<ref>{{citation
Line 18: Line 31:
| year = 1982| s2cid = 16082154
| year = 1982| s2cid = 16082154
| doi-access = free
| doi-access = free
}}.</ref> and their generalizations,<ref>{{citation
}}.</ref> and their generalizations,<ref>N. M. Korneyenko, Combinatorial algorithms on a class of graphs, ''[[Discrete Applied Mathematics]]'', v.54 n.2-3, p.215-217, 1994</ref> which include [[outerplanar graph]]s, as well as for a [[line graph]] of a tree<ref>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</ref><ref>A. Agnetis,
| last = Korneyenko | first = N. M.
P. Detti,
| doi = 10.1016/0166-218X(94)90022-1
C. Meloni,
| issue = 2-3
D. Pacciarelli,
| journal = Discrete Applied Mathematics
⚫
[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</ref>
| mr = 1300246
⚫
or a [[cactus graph]].<ref>
| pages = 215–217
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,
| title = Combinatorial algorithms on a class of graphs
Volume 136, Issue 2-3 (February 2004) 197 - 215
| volume = 54
</ref>
| year = 1994}}</ref> which include [[outerplanar graph]]s, as well as for a [[line graph]] of a tree<ref>{{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}}</ref><ref>{{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}}</ref>
⚫
or a [[cactus graph]].<ref>{{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}}</ref>


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 graph]]s to make them Hamiltonian.<ref>David Gamarnik, Maxim Sviridenko, [https://www.mit.edu/~gamarnik/Papers/HamCompletionPublished.pdf Hamiltonian completions of sparse random graphs], Discrete Applied Mathematics 152 (2005) 139 – 158
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 graph]]s to make them Hamiltonian.<ref>{{citation
| last1 = Gamarnik | first1 = David
</ref>
| 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}}</ref>


==References==
==References==

Revision as of 00:41, 6 February 2024

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

  1. ^ 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
  2. ^ 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.
  3. ^ 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
  4. ^ 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
  5. ^ 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
  6. ^ 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
  7. ^ 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
Retrieved from "https://en.wikipedia.org/w/index.php?title=Hamiltonian_completion&oldid=1203936598"