Premium
Finding Hamilton cycles in random graphs with few queries
Author(s) -
Ferber Asaf,
Krivelevich Michael,
Sudakov Benny,
Vieira Pedro
Publication year - 2016
Publication title -
random structures and algorithms
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.314
H-Index - 69
eISSN - 1098-2418
pISSN - 1042-9832
DOI - 10.1002/rsa.20679
Subject(s) - adjacency list , random graph , combinatorics , struct , property (philosophy) , hamiltonian path , mathematics , order (exchange) , discrete mathematics , computer science , graph , philosophy , epistemology , finance , economics , programming language
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