Approximating maximum independent sets by excluding subgraphs.

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

Ravi Boppana
ravi@cs.nyu.edu
Dept. of Computer Science, New York University, New York.

An approximation algorithm for the maximum independent set problem is given, improving the best performance guarantee known to $\order{n/(\log n)^2}$. We also obtain the same performance guarantee for graph coloring. The results can be combined into a surprisingly strong {\em simultaneous} performance guarantee for the clique and coloring problems. The framework of {\em subgraph-excluding} algorithms is presented. We survey the known approximation algorithms for the independent set (clique), coloring, and vertex cover problems and show how almost all fit into that framework. We show that among subgraph-excluding algorithms, the ones presented achieve the optimal asymptotic performance guarantees.