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 nO(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 G1 and G2 to obtain another graph G0 and ask what is the relationship between xc(STAB(G0)) and xc(STAB(G1)), xc(STAB(G2)). 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.
Additional Metadata
Keywords perfect graph, stable set polytope, extension complexity, communication complexity
THEME Other (theme 6)
Thesis Advisor M. Laurent (Monique) , T. Müller (Tobias) , R.M. de Wolf (Ronald)
Project Approximation Algorithms, Quantum Information and Semidefinite Optimization
Grant This work was funded by the The Netherlands Organisation for Scientific Research (NWO); grant id nwo/617.001.351 - Approximation Algorithms, Quantum Information and Semidefinite Optimization
Citation
Hu, H. (2015, June). On the Extension Complexity of Stable Set Polytopes for Perfect Graphs.