Finding Hidden Cliques in Linear Time with High Probability

We are given a graph G with n vertices, where a random subset of k vertices has been made into a clique, and the remaining edges are chosen independently with probability ½ . This random graph model is denoted G(n, ½ , k). The hidden clique problem is to design an algorithm that finds the k-clique in polynomial time with high probability. An algorithm due to Alon, Krivelevich and Sudakov uses spectral techniques to find the hidden clique with high probability when k = c√n for a sufficiently large constant c > 0. Recently, an algorithm that solves the same problem was proposed by Feige and Ron. It has the advantages of being simpler and more intuitive, and of an improved running time of O(n²). However, the analysis in the paper gives success probability of only 2/3. In this paper we present a new algorithm for finding hidden cliques that both runs in time O(n²), and has a failure probability that is less than polynomially small.