Finding a large hidden clique in a random graph

Noga Mordechai Alon, Michael Krivelevich, Benny Sudakov

Research output: Contribution to conferencePaper

60 Scopus citations

Abstract

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.

Original languageEnglish (US)
Pages594-598
Number of pages5
StatePublished - Dec 1 1998
Externally publishedYes
EventProceedings of the 1998 9th Annual ACM SIAM Symposium on Discrete Algorithms - San Francisco, CA, USA
Duration: Jan 25 1998Jan 27 1998

Other

OtherProceedings of the 1998 9th Annual ACM SIAM Symposium on Discrete Algorithms
CitySan Francisco, CA, USA
Period1/25/981/27/98

All Science Journal Classification (ASJC) codes

  • Software
  • Mathematics(all)

Fingerprint Dive into the research topics of 'Finding a large hidden clique in a random graph'. Together they form a unique fingerprint.

  • Cite this

    Alon, N. M., Krivelevich, M., & Sudakov, B. (1998). Finding a large hidden clique in a random graph. 594-598. Paper presented at Proceedings of the 1998 9th Annual ACM SIAM Symposium on Discrete Algorithms, San Francisco, CA, USA, .