License: Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.APPROX/RANDOM.2022.29
URN: urn:nbn:de:0030-drops-171517
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2022/17151/
Go to the corresponding LIPIcs Volume Portal

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

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

pdf-format:
LIPIcs-APPROX29.pdf (0.8 MB)

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.

BibTeX - Entry

@InProceedings{gao_et_al:LIPIcs.APPROX/RANDOM.2022.29,
  author =	{Gao, Pu and MacRury, Calum and Pra{\l}at, Pawe{\l}},
  title =	{{A Fully Adaptive Strategy for Hamiltonian Cycles in the Semi-Random Graph Process}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2022)},
  pages =	{29:1--29:22},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-249-5},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{245},
  editor =	{Chakrabarti, Amit and Swamy, Chaitanya},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2022/17151},
  URN =		{urn:nbn:de:0030-drops-171517},
  doi =		{10.4230/LIPIcs.APPROX/RANDOM.2022.29},
  annote =	{Keywords: Random graphs and processes, Online adaptive algorithms, Hamiltonian cycles, Differential equation method}
}

Keywords: Random graphs and processes, Online adaptive algorithms, Hamiltonian cycles, Differential equation method
Collection: Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2022)
Issue Date: 2022
Date of publication: 15.09.2022

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI