Prev: ATT/TEL=FIBER
Next: an oracle paradox
From: http://alexslemonade.org on 19 Oct 2009 16:07
Proof. Suppose that G is not a box perfect graph. Since the class of
perfect graphs
is in co-NP, if G is not perfect then there exists a polynomial-time
proof of this,
which also proves that G is not box perfect. Suppose that G is
perfect. By the
results of Gr~tschel, Lov~sz, and Schrijver [24, 25], one can optimize
linear functions
over the stable set polytope of G in polynomial time. By Theorem 4.2,
using the
Gr6tschel, Lov~sz, and Schrijver algorithm polynomially many times we
can prove
that the stable set polytope of G is not a box TDI polyhedron. (Notice
that to verify
that the GrBtschel, Lov~sz, and Schrijver algorithm has optimized a
linear function
over the stable set polytope of G we do not need to verify that G is
perfect, but
only check that the primal and dual solutions produced by the
algorithm are feasible
solutions to the corresponding linear programs and that they give
equal objective
W. Cook / On box TDI polyhedra
values, which can be done in polynomial time since the primal
solutions are integral
and the dual solutions are basic.) []

Proposition 4.5. A graph G is box perfect if and only if G is perfect
and the stable set
polytope of G is a box TDI polyhedron. []
This characterization will be used to prove the following result.
Theorem 4.6. The class of box perfect graphs is in co-NP.
Proof. Suppose that G is not a box perfect graph. Since the class of
perfect graphs
is in co-NP, if G is not perfect then there exists a polynomial-time
proof of this,
which also proves that G is not box perfect. Suppose that G is
perfect. By the
results of Gr~tschel, Lov~sz, and Schrijver [24, 25], one can optimize
linear functions
over the stable set polytope of G in polynomial time. By Theorem 4.2,
using the
Gr6tschel, Lov~sz, and Schrijver algorithm polynomially many times we
can prove
that the stable set polytope of G is not a box TDI polyhedron. (Notice
that to verify
that the GrBtschel, Lov~sz, and Schrijver algorithm has optimized a
linear function
over the stable set polytope of G we do not need to verify that G is
perfect, but
only check that the primal and dual solutions produced by the
algorithm are feasible
solutions to the corresponding linear programs and that they give
equal objective
60 W. Cook / On box TDI polyhedra
values, which can be done in polynomial time since the primal
solutions are integral
and the dual solutions are basic.) []
From: "Brane "Mustav" excap'd" on 19 Oct 2009 22:06
Learn how to format text, you blithering douche-nozzle.


 | 
Pages: 1
Prev: ATT/TEL=FIBER
Next: an oracle paradox