Premium
Finding a large hidden clique in a random graph
Author(s) -
Alon Noga,
Krivelevich Michael,
Sudakov Benny
Publication year - 1998
Publication title -
random structures and algorithms
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.314
H-Index - 69
eISSN - 1098-2418
pISSN - 1042-9832
DOI - 10.1002/(sici)1098-2418(199810/12)13:3/4<457::aid-rsa14>3.0.co;2-w
Subject(s) - combinatorics , mathematics , clique graph , random regular graph , random graph , graph , probabilistic logic , struct , discrete mathematics , time complexity , clique , graph power , computer science , line graph , pathwidth , statistics , programming language
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 > cn 0.5 , for any fixed c >0, thus improving the trivial case k > cn 0.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