Document Open Access Logo

An O(N) Time Algorithm for Finding Hamilton Cycles with High Probability

Authors Rajko Nenadov, Angelika Steger, Pascal Su

PDF
Thumbnail PDF

File

LIPIcs.ITCS.2021.60.pdf
  • Filesize: 0.69 MB
  • 17 pages

Document Identifiers

Author Details

Rajko Nenadov
  • ETH Zürich, Switzerland
Angelika Steger
  • ETH Zürich, Switzerland
Pascal Su
  • ETH Zürich, Switzerland

Funding

  • Su, Pascal: This author was supported by grant no. 200021 169242 of the Swiss National Science Foundation.

Cite As Get BibTex

Rajko Nenadov, Angelika Steger, and Pascal Su. An O(N) Time Algorithm for Finding Hamilton Cycles with High Probability. In 12th Innovations in Theoretical Computer Science Conference (ITCS 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 185, pp. 60:1-60:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021) https://doi.org/10.4230/LIPIcs.ITCS.2021.60

Abstract

We design a randomized algorithm that finds a Hamilton cycle in 𝒪(n) time with high probability in a random graph G_{n,p} with edge probability p ≥ C log n / n. This closes a gap left open in a seminal paper by Angluin and Valiant from 1979.

Subject Classification

ACM Subject Classification
  • Theory of computation → Graph algorithms analysis
  • Mathematics of computing → Random graphs
  • Mathematics of computing → Graph algorithms
  • Mathematics of computing → Matchings and factors
  • Theory of computation → Random walks and Markov chains
Keywords
  • Random Graphs
  • Hamilton Cycle
  • Perfect Matching
  • Linear Time
  • Sublinear Algorithm
  • Random Walk
  • Coupon Collector

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. Miklós Ajtai, János Komlós, and Endre Szemerédi. First occurrence of Hamilton cycles in random graphs. North-Holland Mathematics Studies, 115(C):173-178, 1985. Google Scholar
  2. Peter Allen, Julia Böttcher, Yoshiharu Kohayakawa, and Yury Person. Tight hamilton cycles in random hypergraphs. Random Structures & Algorithms, 46(3):446-465, 2015. Google Scholar
  3. Yahav Alon and Michael Krivelevich. Finding a Hamilton cycle fast on average using rotations and extensions. Random Structures & Algorithms, 57(1):32-46, 2020. Google Scholar
  4. Dana Angluin and Leslie G Valiant. Fast probabilistic algorithms for Hamiltonian circuits and matchings. Journal of Computer and System Sciences, 18(2):155-193, 1979. Google Scholar
  5. Richard Arratia, Andrew D Barbour, and Simon Tavaré. Logarithmic combinatorial structures: a probabilistic approach, volume 1. European Mathematical Society, 2003. Google Scholar
  6. Richard Arratia and Simon Tavaré. The cycle structure of random permutations. The Annals of Probability, pages 1567-1591, 1992. Google Scholar
  7. Tom Bohman and Alan Frieze. Hamilton cycles in 3-out. Random Structures & Algorithms, 35(4):393-417, 2009. Google Scholar
  8. Bela Bollobas, Trevor I. Fenner, and Alan M. Frieze. An algorithm for finding Hamilton paths and cycles in random graphs. Combinatorica, 7(4):327-341, 1987. Google Scholar
  9. Bela Bollobás, Trevor I. Fenner, and Alan M. Frieze. Hamilton cycles in random graphs with minimal degree at least k. A tribute to Paul Erdos, edited by A. Baker, B. Bollobás and A. Hajnal, pages 59-96, 1990. Google Scholar
  10. C.A. Crane. Linear Lists and Priority Queues as Balanced Binary Trees. Computer Science Department. Department of Computer Science, Stanford University., 1972. Google Scholar
  11. Trevor I Fenner and Alan M Frieze. Hamiltonian cycles in random regular graphs. Journal of Combinatorial Theory, Series B, 37(2):103-112, 1984. Google Scholar
  12. Asaf Ferber, Michael Krivelevich, Benny Sudakov, and Pedro Vieira. Finding hamilton cycles in random graphs with few queries. Random Structures & Algorithms, 49(4):635-668, 2016. Google Scholar
  13. Alan Frieze. Hamilton cycles in random graphs: a bibliography. arXiv preprint, 2019. URL: http://arxiv.org/abs/1901.07139.
  14. Alan Frieze, Mark Jerrum, Michael Molloy, Robert Robinson, and Nicholas Wormald. Generating and counting hamilton cycles in random regular graphs. Journal of Algorithms, 21(1):176-198, 1996. Google Scholar
  15. Alan M Frieze. Finding hamilton cycles in sparse random graphs. Journal of Combinatorial Theory, Series B, 44(2):230-250, 1988. Google Scholar
  16. Yuri Gurevich and Saharon Shelah. Expected computation time for Hamiltonian path problem. SIAM Journal on Computing, 16(3):486-502, 1987. Google Scholar
  17. Svante Janson, Tomasz Luczak, and Andrzej Rucinski. Random graphs, volume 45. John Wiley & Sons, 2011. Google Scholar
  18. Donald E Knuth. The art of computer programming: Volume 3: Sorting and Searching. Addison-Wesley Professional, 1998. Google Scholar
  19. János Komlós and Endre Szemerédi. Limit distribution for the existence of Hamiltonian cycles in a random graph. Discrete mathematics, 43(1):55-63, 1983. Google Scholar
  20. Aleksei Dmitrievich Korshunov. Solution of a problem of erdős and renyi on Hamiltonian cycles in nonoriented graphs. Doklady Akademii Nauk, 228(3):529-532, 1976. Google Scholar
  21. Kenneth Maples, Ashkan Nikeghbali, and Dirk Zeindler. On the number of cycles in a random permutation. Electron. Commun. Probab., 17:13 pp., 2012. Google Scholar
  22. Richard Montgomery. Hamiltonicity in random graphs is born resilient. Journal of Combinatorial Theory, Series B, 139:316-341, 2019. Google Scholar
  23. Rajko Nenadov, Angelika Steger, and Miloš Trujić. Resilience of perfect matchings and hamiltonicity in random graph processes. Random Structures & Algorithms, 54(4):797-819, 2019. Google Scholar
  24. Anna Pagh, Rasmus Pagh, and Milan Ruzic. Linear probing with constant independence. In Proceedings of the thirty-ninth annual ACM symposium on Theory of computing, pages 318-327, 2007. Google Scholar
  25. Ben Pfaff. An introduction to binary search trees and balanced trees. Libavl Binary Search Tree Library, 1:19-20, 1998. Google Scholar
  26. Robert W. Robinson and Nicholas C. Wormald. Almost all regular graphs are Hamiltonian. Random Structures & Algorithms, 5(2):363-374, 1994. Google Scholar
  27. Ronitt Rubinfeld and Asaf Shapira. Sublinear time algorithms. SIAM Journal on Discrete Mathematics, 25(4):1562-1588, 2011. Google Scholar
  28. Eli Shamir. How many random edges make a graph Hamiltonian? Combinatorica, 3(1):123-131, 1983. Google Scholar
  29. Benny Sudakov and Van H Vu. Local resilience of graphs. Random Structures & Algorithms, 33(4):409-433, 2008. Google Scholar
  30. Andrew Thomason. A simple linear expected time algorithm for finding a hamilton path. Discrete Mathematics, 75(1-3):373-379, 1989. Google Scholar
  31. Mikkel Thorup and Yin Zhang. Tabulation based 4-universal hashing with applications to second moment estimation. In SODA, volume 4, pages 615-624, 2004. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact