Greed is Good: Approximating Independent Sets in Sparse and Bounded-Degree Graphs

The minimum-degree greedy algorithm, or Greedy for short, is a simple and well-studied method for finding independent sets in graphs. We show that it achieves a performance ratio of (Δ + 2)/3 for approximating independent sets in graphs with degree bounded by Δ. The analysis yields a precise characterization of the size of the independent sets found by the algorithm as a function of the independence number, as well as a generalization of Turán's bound. We also analyze the algorithm when run in combination with a known preprocessing technique, and obtain an improved (2d̄ + 3)/5 performance ratio on graphs with average degree d̄, improving on the previous best (d̄ + 1)/2 of Hochbaum. Finally, we present an efficient parallel and distributed algorithm attaining the performance guarantees of Greedy.