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 sho w that it achieves a performance ratio of (Delta + 2)/3 for approximat ing independent sets in graphs with degree bounded by Delta. The analy sis yields a precise characterization of the size of the independent s ets found by the algorithm as a function of the independence number, a s well as a generalization of Turan's bound. We also analyze the algor ithm when run in combination with a known preprocessing technique, and obtain an improved <(2(d)over bar + 3)/5> performance ratio on graphs with average degree (d) over bar, improving on the previous best <((d )over bar + 1)/2> of Hochbaum. Finally, we present an efficient parall el and distributed algorithm attaining the performance guarantees of G reedy.