On independent sets in random graphs
On independent sets in random graphs
复制标题
DOI：
10.1002/rsa.20550
复制
发表时间：
2010-07
影响因子：
1
通讯作者：
A. Coja-Oghlan;Charilaos Efthymiou
中科院分区：
文献类型：
--
作者：
A. Coja-Oghlan;Charilaos Efthymiou
众所周知，平均度 d = 2m/n 的稀疏随机图 G(n,m) 的独立数为 (2−εd)nln(d)/d≤α(G(n,m))≤(2+εd)nln(d)/d，且在大 d 的极限内，εd→0。此外，一个简单的贪婪算法 w.h.p.找到一组独立的大小为 nln(d)/d 的集合，即大约最大大小的一半。然而，尽管经过 30 年的广泛研究，仍然没有出现有效的算法来为任何固定的 ε>0（独立于 d 和 n）生成大小为 (1+ε)nln(d)/d 的独立集合。在本文中，我们证明随机图中独立集问题的组合结构随着独立集的大小 k 通过点 k∼nln(d)/d 经历相变。粗略地说，我们证明大小 k>(1+ε)nln(d)/d 的独立集合形成了一个复杂崎岖的景观，局部搜索算法似乎陷入困境。我们通过为 Metropolis 过程（用于采样独立集的马尔可夫链）提供指数下界来说明这一现象。 © 2014 Wiley periodicals, Inc. 随机结构。阿尔格., 47, 436–486, 2015
The independence number of a sparse random graph G(n,m) of average degree d = 2m/n is well‐known to be (2−εd)nln(d)/d≤α(G(n,m))≤(2+εd)nln(d)/d with high probability, with εd→0 in the limit of large d. Moreover, a trivial greedy algorithm w.h.p. finds an independent set of size nln(d)/d , i.e., about half the maximum size. Yet in spite of 30 years of extensive research no efficient algorithm has emerged to produce an independent set with size (1+ε)nln(d)/d for any fixed ε>0 (independent of both d and n). 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∼nln(d)/d . Roughly speaking, we prove that independent sets of size k>(1+ε)nln(d)/d form an intricately rugged landscape, in which local search algorithms seem to get stuck. We illustrate this phenomenon by providing an exponential lower bound for the Metropolis process, a Markov chain for sampling independent sets. © 2014 Wiley Periodicals, Inc. Random Struct. Alg., 47, 436–486, 2015