Finding paths in sparse random graphs requires many queries
Preprint
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\sim {\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\sim \mathcal G(n,p)$ when $p=\frac{1+\varepsilon}{n}$ for some fixed constant $\varepsilon>0$. This random graph is known to have typically linearly long paths. To have $\ell$ edges with high probability in $G\sim \mathcal G(n,p)$ one clearly needs to query at least $\Omega\left(\frac{\ell}{p}\right)$ pairs of vertices. Can we find a path of length $\ell$ 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 $\ell=\Omega\left(\frac{\log\left(\frac{1}{\varepsilon}\right)}{\varepsilon}\right)$ with at least constant probability in $G\sim \mathcal G(n,p)$ with $p=\frac{1+\varepsilon}{n}$ must query at least $\Omega\left(\frac{\ell}{p\varepsilon \log\left(\frac{1}{\varepsilon}\right)}\right)$ pairs of vertices. This is tight up to the $\log\left(\frac{1}{\varepsilon}\right)$ factor.
Keywords
All Related Versions
This publication has 6 references indexed in Scilit:
- Anatomy of the giant component: The strictly supercritical regimeEuropean Journal of Combinatorics, 2014
- Sub-Gaussian tail bounds for the width and height of conditioned Galton–Watson treesThe Annals of Probability, 2013
- The phase transition in random graphs: A simple proofRandom Structures & Algorithms, 2012
- Routing complexity of faulty networksRandom Structures & Algorithms, 2007
- On tree census and the giant component in sparse random graphsRandom Structures & Algorithms, 1990
- The longest path in a random graphCombinatorica, 1981