2019/07/18 by Omri Ben‐Eliezer, Ben-Eliezer, Omri, Lior Gishboliner +5 · 1 citation
Biochemistry, Genetics and Molecular Biology · Computer Science · Mathematics · #Algorithms and Data Compression #Combinatorics (math.CO) #DNA and Biological Computing #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics #Limits and Structures in Graph Theory
paper · pdf · doi:10.48550/arxiv.1907.08031
openalex publication_date 2019/07/18 · openalex created_date 2022/07/28 · openalex updated_date 2026/07/28
Semi-random processes involve an adaptive decision-maker, whose goal is to\nachieve some predetermined objective in an online randomized environment. They\nhave algorithmic implications in various areas of computer science, as well as\nconnections to biological processes involving decision making. In this paper,\nwe consider a recently proposed semi-random graph process, described as\nfollows: we start with an empty graph on n vertices, and in each round, the\ndecision-maker, called Builder, receives a uniformly random vertex v, and\nmust immediately (in an online manner) choose another vertex u, adding the\nedge u,v to the graph. Builder's end goal is to make the constructed\ngraph satisfy some predetermined monotone graph property.\n We consider the property of containing a spanning graph H as a subgraph. It\nwas asked by N. Alon whether for any bounded-degree H, Builder can construct\na copy of H w.h.p. in O(n) rounds. We answer this question positively in a\nstrong sense, showing that any graph with maximum degree \Δ can be\nconstructed w.h.p. in (3\Δ/2 + o(\Δ)) n rounds. This is tight (even\nfor the offline case) up to a multiplicative factor of 3 + o\Δ(1).\nFurthermore, for the special case where H is a spanning forest of maximum\ndegree \Δ, we show that H can be constructed w.h.p. in O(n \log\n\Δ) rounds. This is tight up to a multiplicative constant, even for the\noffline setting. Finally, we show a separation between adaptive and\nnon-adaptive strategies, proving a lower bound of \Ω(n\√(\log n)) on\nthe number of rounds necessary to eliminate all isolated vertices w.h.p. using\na non-adaptive strategy. This bound is tight, and in fact there are\nnon-adaptive strategies for constructing a Hamilton cycle or a Kr-factor,\nwhich are successful w.h.p. within O(n\√(\log n)) rounds.\n