Finding Large Independent Sets in Polynomial Expected Time
Amin Coja‐Oghlan · Combinatorics Probability Computing · 2006
We consider instances of the maximum independent set problem that are constructed according to the following semirandom model. Let $G_{n,p}$ be a random graph, and let $S$ be a set of $k$ vertices, chosen uniformly at random. Then, let $G_0$ be the graph obtained by deleting all edges connecting two vertices in $S$ . Finally, an adversary may add edges to $G_0$ 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 $\geq k$ within polynomial expected time , provided that $k\geq C(n/p)^{1/2}$ for a certain constant $C>0$ . Moreover, we prove that in the case $k\leq (1-\varepsilon)\ln(n)/p$ this problem is hard.