[AKS98] Finding a Large Hidden Clique in a Random Graph

Authors: Noga Alon, Michael Krivelevich, Benny Sudakov | Venue: Random Structures & Algorithms, 13(3–4):457–466, 1998

Abstract

We consider the following probabilistic model of a graph on $n$ labeled vertices. First choose a random graph $G(n,1/2)$, and then choose randomly a subset $Q$ of vertices of size $k$ and force it to be a clique by joining every pair of vertices of $Q$ by an edge. The problem is to give a polynomial time algorithm for finding this hidden clique almost surely for various values of $k$. This question was posed independently, in various variants, by Jerrum and by Kučera. In this paper we present an efficient algorithm for all $k>c{n}^{0.5}$, for any fixed $c>0$, thus improving the trivial case $k>c{n}^{0.5}(\log n{)}^{0.5}$. The algorithm is based on the spectral properties of the graph.

BibTeX

Copy

@article{AKS98,
  author  = {Noga Alon and Michael Krivelevich and Benny Sudakov},
  title   = {Finding a Large Hidden Clique in a Random Graph},
  journal = {Random Structures \& Algorithms},
  volume  = {13},
  number  = {3--4},
  pages   = {457--466},
  year    = {1998}
}