| [1] Let and . We can find (close enough)
estimates of these integers in polytime, using the ellipsoid
algorithm to optimize over the theta body. Then will be our
"proxy" for the maximum stable set size and the
proxy for the maximum clique size . |
[2] If
then is not a -partitionable graph.
|
[3] Potatope Slicing Proposition:
If is -partitionable, then is a simplex with integral vertices.
|
| [4] The proposition is the heart of the algorithm. It is
obvious for minimally imperfect graphs and the proof is easy for
partitionable graphs (it uses the same ideas of Bland, Huang,
Trotter and Padberg). We now use the ellipsoid algorithm to either
find affinely independent integral vectors in or show it has a fractional extreme point.
(This algorithm is very similar to several routines in Gr\"otschel,
Lov\'asz, Schrijver.) Similarly, we either deduce
non-partitionability of , or we find integer vectors in . |
| [5] We may now determine partitionability as follows. Let
be the matrix whose row is . For each , find
some such that - if there is no such, then
is not partitionable. Let be the column of a
second matrix . Finally, if , then is
partitionable. Otherwise it is not. |
(*) Vasek Chv\'atal came up with the name "potatope" for the
theta body since it can have smooth parts and pointy bits.