FINDING A LARGE HIDDEN CLIQUE IN A RANDOM GRAPH

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 random ly a subset Q of vertices of size k and force it to be a clique by joi ning 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 va rious variants, by Jerrum and by Kucera. In this paper we present an e fficient algorithm for all k > cn(0.5), for any fixed c > 0, thus impr oving the trivial case k > cn(0.5)(log n)(0.5). The algorithm is based on the spectral properties of the graph. (C) 1998 John Wiley & Sons, Inc.