Very fast construction of bounded-degree spanning graphs via the semi-random graph process

Semi-random processes involve an adaptive decision-maker, whose goal is to achieve some predetermined objective in an online randomized environment. In this paper, we consider a recently proposed semi-random graph process, defined as follows: we start with an empty graph on n vertices, and in each round, the decision-maker, called Builder, receives a uniformly random vertex v, and must immediately (in an online manner) choose another vertex u, adding the edge u, v to the graph. Builder's end goal is to make the constructed graph satisfy some predetermined monotone graph property. There are also natural offline and non-adaptive modifications of this setting.

We consider the property PH of containing a spanning graph H as a subgraph. It was asked by N. Alon whether for every bounded-degree H, Builder can construct a graph satisfying PH with high probability in O(n) rounds. We answer this question positively in a strong sense, showing that any graph with maximum degree ∆ can be constructed with high probability in (3∆/2 + o(∆))n rounds, where the o(∆) term tends to zero as ∆ → ∞. This is tight (even for the offline case) up to a multiplicative factor of 3 + o∆(1). Furthermore, for the special case where H is a forest of maximum degree ∆, we show that H can be constructed with high probability in O(log ∆)n rounds. This is tight up to a multiplicative constant, even for the offline setting. Finally, we show a separation between adaptive and non-adaptive strategies, proving a lower bound of Ω(n √ log n) on the number of rounds necessary to eliminate all isolated vertices w.h.p. using a non-adaptive strategy. This bound is tight, and in fact there are non-adaptive strategies for constructing a Hamilton cycle or a Kr-factor, which are successful w.h.p. within O(n √ log n) rounds.