Approximating Independent Set in Semi-Random Graphs
Bodo Manthey, Kai Plociennik · University of Twente Research Information · 2010
We present an algorithm for the independent set problem on semi-random graphs, which are generated as follows: An adversary chooses an n-vertex graph, and then each edge is flipped independently with a probability of ε> 0. Our algorithm runs in expected polynomial time and guarantees an approximation ratio of roughly O ( √ nε), which beats the inapproximability bounds.