Finding Hamilton cycles in random graphs with few queries

2015/05/04 by Ferber, Asaf, Krivelevich, Michael, Sudakov, Benny +1
#Combinatorics (math.CO) #FOS: Mathematics #Probability (math.PR)

paper · doi:10.48550/arxiv.1505.00730

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 \mathcal G(n,p) in order to typically find a subgraph possessing a given target property. We show that if p≥ (ln n+lnln 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.

Related

• Fast algorithms for solving the Hamilton Cycle problem with high\n probability
• An O(n) time algorithm for finding Hamilton cycles with high probability
• On the number of Hamilton cycles in sparse random graphs
• An almost linear time algorithm for finding Hamilton cycles in sparse random graphs with minimum degree at least three
• Packing, Counting and Covering Hamilton cycles in random directed graphs