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

Magnús M. Halldórsson
Science Institute, University of Iceland, IS-107 Reykjavik, Iceland.

Jaikumar Radhakrishnan
Theoretical Computer Science Group, Tata Institute of Fundamental Research, Bombay, India 400 005. jaikumar@tcs.tifr.res.in

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 (Delta+2)/3 for approximating independent sets in graphs with degree bounded by Delta. 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.

Corrections