Finding Hidden Cliques in Linear Time with High Probability
Yael Dekel, Ori Gurel-Gurevich, Yuval Peres · Combinatorics Probability Computing · 2011
We are given a graphGwithnvertices, where a random subset ofkvertices has been made into a clique, and the remaining edges are chosen independently with probability $\frac12$ . This random graph model is denoted $G(n,\frac12,k)$ . The hidden clique problem is to design an algorithm that finds thek-clique in polynomial time with high probability. An algorithm due to Alon, Krivelevich and Sudakov [3] uses spectral techniques to find the hidden clique with high probability when $k = c \sqrt{n}$ for a sufficiently large constantc> 0. Recently, an algorithm that solves the same problem was proposed by Feige and Ron [12]. It has the advantages of being simpler and more intuitive, and of an improved running time ofO(n2). However, the analysis in [12] gives a success probability of only 2/3. In this paper we present a new algorithm for finding hidden cliques that both runs in timeO(n2) (that is, linear in the size of the input) and has a failure probability that tends to 0 asntends to ∞. We develop this algorithm in the more general setting where the clique is replaced by a dense random graph.