✦ LIBER ✦

Finding and certifying a large hidden clique in a semirandom graph

✍ Scribed by Uriel Feige; Robert Krauthgamer

Publisher: John Wiley and Sons
Year: 2000
Tongue: English
Weight: 150 KB
Volume: 16
Category: Article
ISSN: 1042-9832
DOI: 10.1002/(sici)1098-2418(200003)16:2<195::aid-rsa5>3.0.co;2-a

No coin nor oath required. For personal study only.

✦ Synopsis

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 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.

📜 SIMILAR VOLUMES

Finding a large hidden clique in a rando

Finding a large hidden clique in a random graph

✍ Noga Alon; Michael Krivelevich; Benny Sudakov 📂 Article 📅 1998 🏛 John Wiley and Sons 🌐 English ⚖ 177 KB

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 polynomia

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

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

Thyroid disease and breast cancer: Findi

Thyroid disease and breast cancer: Findings in a large case-control study

✍ A. Kalache; M. P. Vessey; K. McPherson 📂 Article 📅 1982 🏛 John Wiley and Sons 🌐 English ⚖ 261 KB 👁 3 views

The existence of a 2-factor in K1, n-fre

The existence of a 2-factor in K1, n-free graphs with large connectivity and large edge-connectivity

✍ R. E. L. Aldred; Yoshimi Egawa; Jun Fujisawa; Katsuhiro Ota; Akira Saito 📂 Article 📅 2010 🏛 John Wiley and Sons 🌐 English ⚖ 130 KB 👁 1 views

In this article, we study the existence of a 2-factor in a K 1,nfree graph. Sumner [J London Math Soc 13 (1976), 351-359] proved that for n ≥ 4, an (n-1)-connected K 1,n -free graph of even order has a 1-factor.

Finding a way to legality, local coordin

Finding a way to legality, local coordination modes and public policies in large-scale irrigation schemes in Algeria and Morocco

✍ M. Errahj; M. Kuper; N. Faysse; M. Djebbara 📂 Article 📅 2009 🏛 John Wiley and Sons 🌐 English ⚖ 184 KB

## Abstract The design of public policy related to irrigation sectors in North Africa was often based on the state view. Local farmers' organizations, made up of family farms, did not contribute to building the legal framework, which was in turn unable to propose specific solutions for family farmi