A Combinatorial Algorithm for Computing a Maximum Independent Set in a t-perfect Graph

Friedrich Eisenbrand, Stefan Funke, Naveen Garg, Jochen Koenemann

We present a combinatorial polynomial time algorithm to compute a maximum stable set of a $t$-perfect graph. The algorithm rests on an $\epsilon$-approximation algorithm for general set covering and packing problems and is combinatorial in the sense that it does not use an explicit linear programming algorithm or methods from linear algebra or convex geometry. Instead our algorithm is based on basic arithmetic operations and comparisons of rational numbers which are of polynomial binary encoding size in the input.

Proc. of 14th ACM-SIAM Symposium on Discrete Algorithms (SODA) 2003, Baltimore