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.
PDF