Magnús M. HalldórssonAbstract: 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 (Delta+2)/3 for approximating independent sets in graphs with degree bounded by Delta. 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 d. 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 $\Delta$.
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