Greed is good: approximating independent sets in sparse and bounded-degree graphs

Abstract

The minimum-degree Greedy algorithm, or Greedy for short, is one of the simplest, most efficient, and most thoroughly studied methods for finding independent sets in graphs. We show that it surprisingly achieves a performance ratio of (Δ + 2)=3 for approximating independent sets in graphs with degree bounded by Δ. The analysis directs us towards a simple parallel and distributed algorithm with identical performance, which on constant-degree graphs runs in O(log ^∗ n) time using linear number of processors. We also analyze the Greedy algorithm when run in combination with a fractional relaxation technique of Nemhauser and Trotter, and obtain an improved (2d̅ + 3)=5 performance ratio on graphs with average degree ̅. Finally, we introduce a generally applicable technique for improving the approximation ratios of independent set algorithms, and illustrate it by improving the performance ratio of Greedy for large Δ.