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.