On the subgraph query problem

DOI10.1017/S0963548320000218MaRDI QIDQ4993118zbMATH OpenFDO

Authors Ryan Alweiss, Chady Ben Hamida, Xiaoyu He, Alexandre Moreira

Publication date 15 June 2021

Published in Combinatorics, Probability and Computing (Search for Journal in Brave)

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

zbMATH Keywords

Hamilton cyclesqueriessubgraph query problem

Mathematics Subject Classification ID

Eulerian and Hamiltonian graphs (05C45) Random graphs (graph-theoretic aspects) (05C80) Ramsey theory (05D10) Probabilistic methods in extremal combinatorics, including polynomial methods (combinatorial Nullstellensatz, etc.) (05D40) Analysis of algorithms and problem complexity (68Q25)

Abstract: Given a fixed graph $H$, a real number $pin(0,1)$, and an infinite ErdH{o}s-R'enyi graph $GsimG(infty,p)$, how many adjacency queries do we have to make to find a copy of $H$ inside $G$ with probability $1/2$? Determining this number $f(H,p)$ is a variant of the {it subgraph query problem} introduced by Ferber, Krivelevich, Sudakov, and Vieira. For every graph $H$, we improve the trivial upper bound of $f(H,p)=O(p^{-d})$, where $d$ is the degeneracy of $H$, by exhibiting an algorithm that finds a copy of $H$ in time $o(p^{-d})$ as $p$ goes to $0$. Furthermore, we prove that there are $2$-degenerate graphs which require $p^{-2+o(1)}$ queries, showing for the first time that there exist graphs $H$ for which $f(H,p)$ does not grow like a constant power of $p^{-1}$ as $p$ goes to $0$. Finally, we answer a question of Feige, Gamarnik, Neeman, R'acz, and Tetali by showing that for any $delta<2$, there exists $alpha<2$ such that one cannot find a clique of order $alphalo{g}_{2}n$ in $G(n,1/2)$ in $n^{d}elta$ queries.

Recommendations

• Finding Hamilton cycles in random graphs with few queries
• Finding paths in sparse random graphs requires many queries
• On approximating the number of k-cliques in sublinear time
• Online Ramsey numbers and the subgraph query problem
• Learning graph based quantum query algorithms for finding constant-size subgraphs

Cites work

• A new approach to the planted clique problem
• Cliques in random graphs
• Finding cliques using few probes
• Finding Hamilton cycles in random graphs with few queries
• Finding paths in sparse random graphs requires many queries
• scientific article; zbMATH DE number 3494449 (Why is no real title available?)
• Online Ramsey numbers and the subgraph query problem
• Positional games
• Positional games
• Ramsey numbers of degenerate graphs
• The longest path in a random graph
• The probabilistic method. With an appendix on the life and work of Paul Erdős.

Cited in

(4)

• Intersection graphs of \(k\)-acyclic families of subtrees and relational database query processing.
• Finding paths in sparse random graphs requires many queries
• Approximate Discovery of Random Graphs
• Finding cliques and dense subgraphs using edge queries

This page was built for publication: On the subgraph query problem

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