Finding paths in sparse random graphs requires many queries

DOI10.1002/RSA.20680MaRDI QIDQ2951884zbMATH OpenOpenAlexFDO

Authors

Publication date 10 January 2017

Published in Random Structures \& Algorithms (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1505.00734

zbMATH Keywords

economicpathsqueriesrandom graphs

Mathematics Subject Classification ID

Paths and cycles (05C38) Density (toughness, etc.) (05C42) Random graphs (graph-theoretic aspects) (05C80)

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 $GsimmathcalG(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 $GsimmathcalG(n,p)$ when $p=frac1+varepsilonn$ 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 $GsimmathcalG(n,p)$ one clearly needs to query at least $Omegaleft(fracellpight)$ 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=Omegaleft(fraclogleft(frac1varepsilonight)varepsilonight)$ with at least constant probability in $GsimmathcalG(n,p)$ with $p=frac1+varepsilonn$ must query at least $Omegaleft(fracellpvarepsilonlogleft(frac1varepsilonight)ight)$ pairs of vertices. This is tight up to the $logleft(frac1varepsilonight)$ factor.

Recommendations

• Finding Hamilton cycles in random graphs with few queries
• On the subgraph query problem
• On large induced trees and long induced paths in sparse random graphs
• Approximate Discovery of Random Graphs
• Paths and cycles in random subgraphs of graphs with large minimum degree

Cites work

• Anatomy of the giant component: the strictly supercritical regime
• Finding Hamilton cycles in random graphs with few queries
• scientific article; zbMATH DE number 986986 (Why is no real title available?)
• scientific article; zbMATH DE number 1246231 (Why is no real title available?)
• On tree census and the giant component in sparse random graphs
• Proofs from THE BOOK
• Sub-Gaussian tail bounds for the width and height of conditioned Galton-Watson trees
• The Galton-Watson process conditioned on the total progeny
• The longest path in a random graph
• The phase transition in random graphs: a simple proof
• Une théorie combinatoire des séries formelles

Cited in

(9)

• An adversarial model for scheduling with testing
• Topology discovery of sparse random graphs with few participants
• Finding Hamilton cycles in random graphs with few queries
• Finding hidden hubs and dominating sets in sparse graphs by randomized neighborhood queries
• Online Ramsey numbers and the subgraph query problem
• Approximate Discovery of Random Graphs
• On the subgraph query problem
• Finding a planted clique by adaptive probing
• Finding cliques and dense subgraphs using edge queries

This page was built for publication: Finding paths in sparse random graphs requires many queries

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2951884)