• search hit 16 of 28
Back to Result List

Finding large independent sets in polynomial expected time

Please always quote using this URN:urn:nbn:de:0296-matheon-2789
  • We consider instances of the maximum independent set problem that are constructed according to the following semirandom model. Let Gn,p be a random graph, and let S be a set of k vertices, chosen uniformly at random. Then, let G0 be the graph obtained by deleting all edges connecting two vertices in S. Finally, an adversary may add edges to G0 that do not connect two vertices in S, thereby producing the instance G = G ∗ n,p,k . We present an algorithm that on input G = G ∗ n,p,k finds an independent set of size ≥ k within polynomial expected time, provided that k ≥ C(n/p)1/2 for a certain constant C > 0. Moreover, we prove that in the case k ≤ (1 − ε) ln(n)/p this problem is hard.

Download full text files

Export metadata

Additional Services

Share in Twitter Search Google Scholar
Metadaten
Author:Amin Coja-Oghlan
URN:urn:nbn:de:0296-matheon-2789
Referee:Hans Jürgen Prömel
Document Type:Preprint, Research Center Matheon
Language:English
Date of first Publication:2005/05/11
Release Date:2005/10/31
Institute:Humboldt-Universität zu Berlin
Preprint Number:278
Verstanden ✔
Diese Webseite verwendet technisch erforderliche Session-Cookies. Durch die weitere Nutzung der Webseite stimmen Sie diesem zu. Unsere Datenschutzerklärung finden Sie hier.