The Greedier the Better: An Efficient Algorithm for Approximating Maximum Independent Set

The classical greedy heuristic for approximating maximum independent set is simple and efficient. It achieves a performance ratio of (Δ + 2)/3, where Δ is the maximum node degree of the input graph. All known algorithms for the problem with better performance ratios are much more complicated and inefficient. In this paper, we propose a natural extension of the greedy heuristic. It is as simple and as efficient as the classical greedy heuristic. By a careful analysis on the structure of the intermediate graphs manipulated by our heuristic, we prove that the performance ratio is improved to (Δ + 3)/3.25.link_to_subscribed_fulltex