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.00734
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∼ \mathcal 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∼ \mathcal 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∼ \mathcal 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∼ \mathcal 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.