Finding Paths in Sparse Random Graphs Requires Many Queries

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 similar to 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 similar to G(n, p) when p = 1+epsilon/n for some fixed constant epsilon > 0. This random graph is known to have typically linearly long paths. To have l edges with high probability in G similar to G(n, p) one clearly needs to query at least Omega(l/p) pairs of vertices. Can we find a path of length l 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 l = Omega(log(1/epsilon)/epsilon) with at least constant probability in G similar to G(n, p) with p = 1+epsilon/n must query at least Omega(l/p epsilon log(1/epsilon)) pairs of vertices. This is tight up to the log(1/epsilon) factor. (C) 2016 Wiley Periodicals, Inc.