On Finding Randomly Planted Cliques in Arbitrary Graphs

We study a planted clique model introduced by Feige [18] where a complete graph of size c · n is planted uniformly at random in an arbitrary n-vertex graph. We give a simple deterministic algorithm that, in almost linear time, recovers a clique of size (c/3)O(1/c) · n as long as the original graph has maximum degree at most (1-p)n for some fixed p > 0. The proof hinges on showing that the degrees of the final graph are correlated with the planted clique, in a way similar to (but more intricate than) the classical G(n, 1/2) + K√n planted clique model. Our algorithm suggests a separation from the worst-case model, where, assuming the Unique Games Conjecture, no polynomial algorithm can find cliques of size Ω(n) for every fixed c > 0, even if the input graph has maximum degree (1-p)n. Our techniques extend beyond the planted clique model. For example, when the planted graph is a balanced biclique, we recover a balanced biclique of size larger than the best guarantees known for the worst case.