The Library
On independent sets in random graphs
Tools
Tools
Tools
Coja-Oghlan, Amin and Efthymiou, Charilaos (2011) On independent sets in random graphs. In: Twenty-Second Annual ACM-SIAM Symposium on Discrete Algorithms, San Francisco, CA, USA, 23 - 25 Jan 2011. Published in: SODA '11 Proceedings of the Twenty-Second Annual ACM-SIAM Symposium on Discrete Algorithms pp. 136-144.
Research output not available from this repository.
Request-a-Copy directly from author or use local Library Get it For Me service.
Abstract
The independence number of a sparse random graph G(n, m) of average degree d = 2m/n is well-known to be α(G(n, m)) ~ 2n ln(d)/d with high probability. Moreover, a trivial greedy algorithm w.h.p. finds an independent set of size (1 + o(1)) · n ln(d)/d, i.e., half the maximum size. Yet in spite of 30 years of extensive research no efficient algorithm has emerged to produce an independent set with (1 + ε)n ln(d)/d, for any fixed ε > 0. In this paper we prove that the combinatorial structure of the independent set problem in random graphs undergoes a phase transition as the size k of the independent sets passes the point k ~ n ln(d)/d. Roughly speaking, we prove that independent sets of size k > (1 + ε)n ln(d)/d form an intricately ragged landscape, in which local search algorithms are bound to get stuck. We illustrate this phenomenon by providing an exponential lower bound for the Metropolis process, a Markov chain for sampling independents sets.
| Item Type: | Conference Item (Paper) | ||||
|---|---|---|---|---|---|
| Subjects: | Q Science > QA Mathematics | ||||
| Divisions: | Faculty of Science, Engineering and Medicine > Science > Mathematics | ||||
| Journal or Publication Title: | SODA '11 Proceedings of the Twenty-Second Annual ACM-SIAM Symposium on Discrete Algorithms | ||||
| Publisher: | SIAM | ||||
| Official Date: | 2011 | ||||
| Dates: |
|
||||
| Page Range: | pp. 136-144 | ||||
| Status: | Peer Reviewed | ||||
| Publication Status: | Published | ||||
| Access rights to Published version: | Restricted or Subscription Access | ||||
| Conference Paper Type: | Paper | ||||
| Title of Event: | Twenty-Second Annual ACM-SIAM Symposium on Discrete Algorithms | ||||
| Type of Event: | Other | ||||
| Location of Event: | San Francisco, CA, USA | ||||
| Date(s) of Event: | 23 - 25 Jan 2011 |
Request changes or add full text files to a record
Repository staff actions (login required)
 |
View Item |
