We consider a variant of the planted clique problem where we are allowed unbounded computational time but can only investigate a small part of the graph by adaptive edge queries. We determine (up to logarithmic factors) the number of queries necessary both for detecting the presence of a planted clique and for finding the planted clique. Specifically, let @math be a random graph on @math vertices with a planted clique of size @math . We show that no algorithm that makes at most @math adaptive queries to the adjacency matrix of @math is likely to find the planted clique. On the other hand, when @math there exists a simple algorithm (with unbounded computational power) that finds the planted clique with high probability by making @math adaptive queries. For detection, the additive @math term is not necessary: the number of queries needed to detect the presence of a planted clique is @math (up to logarithmic factors).
This paper is a natural follow-up to the recent work of Feige, Gamarnik, Neeman, R 'acz, and Tet ali @cite_9 , where the authors consider the problem of finding cliques in an Erd o s-R 'enyi random graph under the same adaptive edge query model. While the largest clique in a random graph with edge density @math has size approximately @math , the current best algorithm that makes at most @math adaptive edge queries finds a clique of size approximately @math ---closing the gap between these two bounds is an open problem. Feige et al. @cite_9 show an impossibility result if the adaptivity of the algorithm is limited: any algorithm that makes @math edge queries ( @math ) in @math rounds finds cliques of size at most @math where @math .
@cite_9
2962704928 2166602562 1613681423 2078758709
Consider an Erdos---Renyi random graph in which each edge is present independently with probability @math 1 2, except for a subset @math CN of the vertices that form a clique (a completely connected subgraph). We consider the problem of identifying the clique, given a realization of such a random graph. The algorithm of (ANALCO. SIAM, pp 67---75, 2011) provably identifies the clique @math CN in linear time, provided @math |CN|?1.261N. Spectral methods can be shown to fail on cliques smaller than @math N. In this paper we describe a nearly linear-time algorithm that succeeds with high probability for @math |CN|?(1+?)N e for any @math ?>0. This is the first algorithm that provably improves over spectral methods. We further generalize the hidden clique problem to other background graphs (the standard case corresponding to the complete graph on @math N vertices). For large-girth regular graphs of degree @math (Δ+1) we prove that so-called local algorithms succeed if @math |CN|?(1+?)N eΔ and fail if @math |CN|≤(1-?)N eΔ. 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 Kucera. In this paper we present an efficient algorithm for all k>cn0.5, for any fixed c>0, thus improving the trivial case k>cn0.5(log n)0.5. The algorithm is based on the spectral properties of the graph. © 1998 John Wiley & Sons, Inc. Random Struct. Alg., 13: 457–466, 1998 This paper studies the problem of detecting the presence of a small dense community planted in a large Erd o s-R 'enyi random graph @math , where the edge probability within the community exceeds @math by a constant factor. Assuming the hardness of the planted clique detection problem, we show that the computational complexity of detecting the community exhibits the following phase transition phenomenon: As the graph size @math grows and the graph becomes sparser according to @math , there exists a critical value of @math , below which there exists a computationally intensive procedure that can detect far smaller communities than any computationally efficient procedure, and above which a linear-time procedure is statistically optimal. The results also lead to the average-case hardness results for recovering the dense community and approximating the densest @math -subgraph. Alon, Krivelevich, and Sudakov [Random Struct Algorithms 13(3–4) (1998), 457–466.] designed an algorithm based on spectral techniques that almost surely finds a clique of size hidden in an otherwise random graph. We show that a different algorithm, based on the Lovasz theta function, almost surely both finds the hidden clique and certifies its optimality. Our algorithm has an additional advantage of being more robust: it also works in a semirandom hidden clique model, in which an adversary can remove edges from the random portion of the graph. ©2000 John Wiley & Sons, Inc. Random Struct. Alg., 16, 195–208, 2000