Document Open Access Logo

A Fully Adaptive Strategy for Hamiltonian Cycles in the Semi-Random Graph Process

Authors Pu Gao, Calum MacRury, Paweł Prałat

PDF
Thumbnail PDF

File

LIPIcs.APPROX-RANDOM.2022.29.pdf
  • Filesize: 0.82 MB
  • 22 pages

Document Identifiers

Author Details

Pu Gao
  • Department of Combinatorics and Optimization, University of Waterloo, Canada
Calum MacRury
  • Department of Computer Science, University of Toronto, Canada
Paweł Prałat
  • Department of Mathematics, Toronto Metropolitan University, Canada

Acknowledgements

The numerical results presented in this paper were obtained using the Julia language [J. Bezanson et al., 2017]. We would like to thank Bogumił Kamiński from SGH Warsaw School of Economics for helping us to implement it. The program is available on-line.

Cite As Get BibTex

Pu Gao, Calum MacRury, and Paweł Prałat. A Fully Adaptive Strategy for Hamiltonian Cycles in the Semi-Random Graph Process. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 245, pp. 29:1-29:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022) https://doi.org/10.4230/LIPIcs.APPROX/RANDOM.2022.29

Abstract

The semi-random graph process is a single player game in which the player is initially presented an empty graph on n vertices. In each round, a vertex u is presented to the player independently and uniformly at random. The player then adaptively selects a vertex v, and adds the edge uv to the graph. For a fixed monotone graph property, the objective of the player is to force the graph to satisfy this property with high probability in as few rounds as possible.
We focus on the problem of constructing a Hamiltonian cycle in as few rounds as possible. In particular, we present an adaptive strategy for the player which achieves it in α n rounds, where α < 2.01678 is derived from the solution to some system of differential equations. We also show that the player cannot achieve the desired property in less than β n rounds, where β > 1.26575. These results improve the previously best known bounds and, as a result, the gap between the upper and lower bounds is decreased from 1.39162 to 0.75102.

Subject Classification

ACM Subject Classification
  • Theory of computation → Randomness, geometry and discrete structures
Keywords
  • Random graphs and processes
  • Online adaptive algorithms
  • Hamiltonian cycles
  • Differential equation method

Metrics

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

Related Versions

References

  1. Natalie Behague, Trent Marbach, Paweł Prałat, and Andrzej Ruciński. Subgraph games in the semi-random graph process and its generalization to hypergraphs. arXiv preprint, 2022. URL: https://doi.org/10.48550/ARXIV.2105.07034.
  2. Omri Ben-Eliezer, Lior Gishboliner, Dan Hefetz, and Michael Krivelevich. Very fast construction of bounded-degree spanning graphs via the semi-random graph process. Proceedings of the 31st Symposium on Discrete Algorithms (SODA'20), pages 728-737, 2020. Google Scholar
  3. Omri Ben-Eliezer, Dan Hefetz, Gal Kronenberg, Olaf Parczyk, Clara Shikhelman, and Miloš Stojaković. Semi-random graph process. Random Structures & Algorithms, 56(3):648-675, 2020. Google Scholar
  4. Patrick Bennett and Andrzej Dudek. A gentle introduction to the differential equation method and dynamic concentration. CoRR, 2020. URL: https://doi.org/10.48550/ARXIV.2007.01994.
  5. J. Bezanson, A. Edelman, S. Karpinski, and V.B. Shah. Julia: A fresh approach to numerical computing. SIAM review, 59(1):65-98, 2017. Google Scholar
  6. Tom Bohman and Alan Frieze. Hamilton cycles in 3-out. Random Structures & Algorithms, 35(4):393-417, 2009. Google Scholar
  7. Sofiya Burova and Lyuben Lichev. The semi-random tree process, 2022. URL: https://doi.org/10.48550/ARXIV.2204.07376.
  8. Alan M Frieze. Maximum matchings in a class of random graphs. Journal of Combinatorial Theory, Series B, 40(2):196-212, 1986. Google Scholar
  9. Pu Gao, Bogumił Kamiński, Calum MacRury, and Paweł Prałat. Hamilton cycles in the semi-random graph process. European Journal of Combinatorics, 99:103423, 2022. URL: https://doi.org/10.1016/j.ejc.2021.103423.
  10. Pu Gao, Calum MacRury, and Pawel Pralat. A fully adaptive strategy for hamiltonian cycles in the semi-random graph process. CoRR, abs/2205.02350, 2022. URL: https://doi.org/10.48550/ARXIV.2205.02350.
  11. Pu Gao, Calum MacRury, and Paweł Prałat. Perfect matchings in the semi-random graph process. SIAM Journal on Discrete Mathematics, in press, 2022. Google Scholar
  12. Michal Karoński, Ed Overman, and Boris Pittel. On a perfect matching in a random digraph with average out-degree below two. Journal of Combinatorial Theory, Series B, 143, March 2020. URL: https://doi.org/10.1016/j.jctb.2020.03.004.
  13. Calum MacRury and Erlang Surya. Sharp thresholds in adaptive random graph processes. CoRR, 2022. Google Scholar
  14. Lutz Warnke. On wormald’s differential equation method. CoRR, abs/1905.08928, 2019. URL: https://doi.org/10.48550/ARXIV.1905.08928.
  15. Nicholas C Wormald. The differential equation method for random graph processes and greedy algorithms. Lectures on approximation and randomized algorithms, 73:155, 1999. 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