TY - JOUR

T1 - Finding a large hidden clique in a random graph

AU - Alon, Noga

AU - Krivelevich, Michael

AU - Sudakov, Benny

N1 - Copyright:
Copyright 2020 Elsevier B.V., All rights reserved.

PY - 1998

Y1 - 1998

N2 - 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 Kučera. 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.

AB - 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 Kučera. 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.

UR - http://www.scopus.com/inward/record.url?scp=0032221884&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=0032221884&partnerID=8YFLogxK

U2 - 10.1002/(sici)1098-2418(199810/12)13:3/4<457::aid-rsa14>3.0.co;2-w

DO - 10.1002/(sici)1098-2418(199810/12)13:3/4<457::aid-rsa14>3.0.co;2-w

M3 - Article

AN - SCOPUS:0032221884

VL - 13

SP - 457

EP - 466

JO - Random Structures and Algorithms

JF - Random Structures and Algorithms

SN - 1042-9832

IS - 3-4

ER -