Finding Hamilton cycles in random graphs with few queries1. Issue 4 (27th September 2016) - Ferber, Asaf; Krivelevich, Michael; Sudakov, Benny; Vieira, Pedro
Abstract: We introduce a new setting of algorithmic problems in random graphs, studying the minimum number of queries one needs to ask about the adjacency between pairs of vertices of G ( n, p ) in order to typically find a subgraph possessing a given target property. We show that if p ≥ ln n + ln ln n + ω ( 1 ) n, then one can find a Hamilton cycle with high probability after exposing ( 1 + o ( 1 ) ) n edges. Our result is tight in both p and the number of exposed edges. © 2016 Wiley Periodicals, Inc. Random Struct. Alg., 49, 635–668, 2016