A combinatorial algorithm for computing a maximum independent set in a t-perfect graph
Friedrich Eisenbrand, Stefan Funke, Naveen Garg, Jochen Könemann · 2003
We present a combinatorial polynomial time algorithm to compute a maximum stable set of a $t$-perfect graph. The algorithm rests on an $e$-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.