## Improved Approximations of Independent Sets in Bounded-Degree Graphs via Subgraph Removal

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

Finding maximum independent sets in graphs with bounded maximum degree Delta
is a well-studied NP-complete problem. We introduce an algorithm
schema for improving the approximation of algorithms for this problem,
which is based on preprocessing the input by removing cliques.
We give an implementation of a theorem on the independence number of
clique-free graphs, and use it to obtain an O(Delta/loglog Delta)
performance ratio with out schema. This is the first o(Delta) ratio
for the independent set problem. We also obtain an efficient method
with a Delta/6 (1 + o(1)) performance ratio, improving on the best
performance ratio known for intermediate values of Delta.