✦ LIBER ✦

Finding a large hidden clique in a random graph

✍ Scribed by Noga Alon; Michael Krivelevich; Benny Sudakov

Publisher: John Wiley and Sons
Year: 1998
Tongue: English
Weight: 177 KB
Volume: 13
Category: Article
ISSN: 1042-9832
DOI: 10.1002/(sici)1098-2418(199810/12)13:3/4<457::aid-rsa14>3.0.co;2-w

No coin nor oath required. For personal study only.

✦ Synopsis

We consider the following probabilistic model of a graph on n labeled vertices.

Ž

. First choose a random graph G n, 1r2 , 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 ) cn 0.5 , for ˇ0.5 Ž . 0.5 any fixed c ) 0, thus improving the trivial case k ) cn log n . The algorithm is based on the spectral properties of the graph.

📜 SIMILAR VOLUMES

Finding and certifying a large hidden cl

Finding and certifying a large hidden clique in a semirandom graph

✍ Uriel Feige; Robert Krauthgamer 📂 Article 📅 2000 🏛 John Wiley and Sons 🌐 English ⚖ 150 KB

designed an algorithm based on spectral techniques that almost surely finds a clique of size √ n hidden in an otherwise random graph. We show that a different algorithm, based on the Lovász theta function, almost surely both finds the hidden clique and certifies its optimality. Our algorithm has an

Finding hidden hubs and dominating sets

Finding hidden hubs and dominating sets in sparse graphs by randomized neighborhood queries

✍ Peter Damaschke 📂 Article 📅 2010 🏛 John Wiley and Sons 🌐 English ⚖ 100 KB

An algorithm for finding a large indepen

An algorithm for finding a large independent set in planar graphs

✍ Norishige Chiba; Takao Nishizeki; Nobuji Saito 📂 Article 📅 1983 🏛 John Wiley and Sons 🌐 English ⚖ 333 KB 👁 1 views

Vertices of given degree in a random gra

Vertices of given degree in a random graph

✍ Béla Bollobás 📂 Article 📅 1982 🏛 John Wiley and Sons 🌐 English ⚖ 349 KB 👁 1 views

An upper bound on the size of a largest

An upper bound on the size of a largest clique in a graph

✍ Dennis P. Geoffroy; David P. Sumner 📂 Article 📅 1978 🏛 John Wiley and Sons 🌐 English ⚖ 308 KB 👁 1 views

## Abstract A graph is point determining if distinct vertices have distinct neighborhoods. The nucleus of a point‐determining graph is the set __G__^O^ of all vertices, __v__, such that __G__–__v__ is point determining. In this paper we show that the size, ω(__G__), of a maximum clique in __G__ sat

Large deviations for random walks in a r

Large deviations for random walks in a random environment

✍ S. R. S. Varadhan 📂 Article 📅 2003 🏛 John Wiley and Sons 🌐 English ⚖ 253 KB 👁 1 views