On the Extension Complexity of Stable Set Polytopes for Perfect Graphs

In linear programming one can formulate many combinatorial optimization problems as optimizing a linear function over a feasible region that is a polytope. Given a polytope P, any non-redundant description of P contains precisely one inequality for each facet. A polytope Q is called an extension of P if π(Q) = P under some affine mapping π. Notice that Q could be in higher dimensional space than 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. If P has small extension complexity, one can optimize over P by means of a small linear program. This motivates the study of upper and lower bounds on extension complexity. In fact, Yannakakis [25] showed that the extension complexity of P is equal to the non-negative rank of the slack matrix of P. Moreover, there is a link between extension complexity and communication complexity, and one can often obtain lower bounds on extension complexity from lower bounds on nondeterministic communication complexity. Yannakakis [25] proved an upper bound n^{O(log n)} for the extension complexities of the stable set polytopes of perfect graphs. Chudnovsky et al. [6] 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 extension complexity and graph operations. The thesis starts with a global overview of extension complexity and its connection with communication theory. We then study the extension complexity of stable set polytopes, denoted by xc(STAB(G)), for some graphs G. One can apply graph operations to graphs G₁ and G₂ to obtain another graph G₀ and ask what is the relationship between xc(STAB(G₀)) and xc(STAB(G₁)), xc(STAB(G₂)). We also consider some special graphs. It is not clear whether the extension complexity of the stable set polytope of perfect graphs is polynomial or not. Nevertheless, we are able to show that the extension complexities of the stable set polytopes of double-split graphs are polynomial. Furthermore, we provide an upper bound on the extension complexity of any perfect graph G depending on the depth of a decomposition tree of G. We also study the extension complexity of other subclasses of perfect graphs as well, for example, Meyniel graphs.