On the Extension Complexity of Stable Set Polytopes for Perfect Graphs

Abstract

In linear programming one can formulate many combinatorial optimization problems as optimizing a linear function over a feasible region that is a polytope. A polytope Q is called an extension of P if Q has an (affine) linear projection into P. The extension complexity xc(P) of P is defined as the minimum number of facets among all polytopes Q that are extensions of P. Yannakakis proved an upper bound n^{O(log n)} for the extension complexities of the stable set polytopes of perfect graphs. On the other hand, the stable set polytopes of perfect graphs are captured by a polynomial-sized semidefinite programming. It is still an open question whether the extension complexities of the stable set polytopes of perfect graphs are polynomial. Chudnovsky et al. showed that every perfect graph either forms one of the basic perfect graphs or it admits one of the structural decompositions. These results motivate our study of the extension complexity of the stable set polytope of perfect graphs.

In this presentation, we start with a global overview of extension complexity and its connection with communication theory. Then we present our result on the extension complexity of the stable set polytope of graphs under some graph operation. Finally, we provide an upper bound on the extension complexity of any perfect graph G depending on the depth of a decomposition tree of G.