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 ${\alpha }_{\star }(\delta ,\ell )$ be the supremum over $\alpha$ such that there exists an algorithm that makes $n^{\delta }$ queries in total to the adjacency matrix of $G$, in a constant $\ell$ number of rounds, and outputs a clique of size $\alpha {\log }_{2}n$ with high probability. We give improved upper bounds on ${\alpha }_{\star }(\delta ,\ell )$ for every $\delta \in [1,2)$ and $\ell \ge 3$. We also study analogous questions for finding subgraphs with density at least $\eta$ for a given $\eta$, and prove corresponding impossibility results.

19 pp, 5 figures, Focused Workshop on Networks and Their Limits held at the Erdős Center, Budapest, Hungary in July 2023