Magnús M. HalldórssonFinding maximum independent sets in graphs with bounded maximum degree is a well-studied NP-complete problem. We study two approaches for finding approximate solutions, and obtain several improved performance ratios. The first is a subgraph removal schema introduced in our previous paper. Using better component algorithms, we obtain an efficient method with a $\Delta/6 (1 + o(1))$ performance ratio. We then produce an implementation of a theorem of Ajtai et al. on the independence number of clique-free graphs, and use it to obtain a $O(\Delta/\log\log \Delta)$ performance ratio with our schema. This is the first o(Delta) ratio. The second is a local search method of Berman and Füaut;rer for which they proved a fine performance ratio but by using extreme amounts of time. We show how to substantially decrease the computing requirements while maintaining the same performance ratios of roughly (Delta+3)/5 for graphs with maximum degree $\Delta$. We then show that a scaled-down version of their algorithm yields a (Delta+3)/4 performance, improving on previous bounds for reasonably efficient methods.
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