Finding Hamilton cycles in random graphs with few queries1. Issue 4 (27th September 2016)

• Record Type: Journal Article
• Authors: Ferber, Asaf; Krivelevich, Michael; Sudakov, Benny; Vieira, Pedro
• Is Part Of: Random structures & algorithms. Volume 49:Issue 4(2016)
• Page Start: 635
• Page End: 668
• Publication Date: 2016-09-27
• Subjects: random graphs -- Hamiltonicity -- Hamilton cycles -- queries -- economic; Random graphs -- Periodicals; Mathematical analysis -- Periodicals; 519
• DOI: 10.1002/rsa.20679
• Languages: English
• ISSNs: 1042-9832

Abstract

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