Finding cliques and dense subgraphs using edge queries
Abstract
We consider the problem of finding a large clique in an Erdős--Rényi random graph where we are allowed unbounded computational time but can only query a limited number of edges. Recall that the largest clique in $G \sim G(n,1/2)$ has size roughly $2\log_{2} n$. Let $α_{\star}(δ,\ell)$ be the supremum over $α$ such that there exists an algorithm that makes $n^δ$ queries in total to the adjacency matrix of $G$, in a constant $\ell$ number of rounds, and outputs a clique of size $α\log_{2} n$ with high probability. We give improved upper bounds on $α_{\star}(δ,\ell)$ for every $δ\in [1,2)$ and $\ell \geq 3$. We also study analogous questions for finding subgraphs with density at least $η$ for a given $η$, and prove corresponding impossibility results.
Fields of Study & Subjects
Complexity and Algorithms in Graphs
Machine Learning and Algorithms
Optimization and Search Problems
Publication details
- Journal / source
- Discrete Mathematics
- Publisher
- Elsevier BV
- Volume
- 349
- Issue
- 10
- Pages
- 115226–115226
- Publication date
- 15 May 2026
- Language
- EN