Finding paths in sparse random graphs requires many queries1. Issue 1 (29th September 2016)

• Record Type: Journal Article
• Authors: Ferber, Asaf; Krivelevich, Michael; Sudakov, Benny; Vieira, Pedro
• Is Part Of: Random structures & algorithms. Volume 50:Issue 1(2017)
• Page Start: 71
• Page End: 85
• Publication Date: 2016-09-29
• Subjects: random graphs -- paths -- queries -- economic; Random graphs -- Periodicals; Mathematical analysis -- Periodicals; 519
• DOI: 10.1002/rsa.20680
• Languages: English
• ISSNs: 1042-9832

Abstract

Abstract: We discuss a new algorithmic type of problem in random graphs studying the minimum number of queries one has to ask about adjacency between pairs of vertices of a random graph G ∼ G ( n, p ) in order to find a subgraph which possesses some target property with high probability. In this paper we focus on finding long paths in G ∼ G ( n, p ) when p = 1 + ε n for some fixed constant ε > 0 . This random graph is known to have typically linearly long paths. To have ℓ edges with high probability in G ∼ G ( n, p ) one clearly needs to query at least Ω ( ℓ p ) pairs of vertices. Can we find a path of length ℓ economically, i.e., by querying roughly that many pairs? We argue that this is not possible and one needs to query significantly more pairs. We prove that any randomised algorithm which finds a path of length ℓ = Ω ( log ( 1 ε ) ε ) with at least constant probability in G ∼ G ( n, p ) with p = 1 + ε n must query at least Ω ( ℓ p ε log ( 1 ε ) ) pairs of vertices. This is tight up to the log ( 1 ε ) factor. © 2016 Wiley Periodicals, Inc. Random Struct. Alg., 50, 71–85, 2017