View Item 
        •   Utrecht University Student Theses Repository Home
        • UU Theses Repository
        • Theses
        • View Item
        •   Utrecht University Student Theses Repository Home
        • UU Theses Repository
        • Theses
        • View Item
        JavaScript is disabled for your browser. Some features of this site may not work without it.

        Browse

        All of UU Student Theses RepositoryBy Issue DateAuthorsTitlesSubjectsThis CollectionBy Issue DateAuthorsTitlesSubjects

        On the Extension Complexity of Stable Set Polytopes for Perfect Graphs

        Thumbnail
        View/Open
        Extension.pdf (435.7Kb)
        Publication date
        2015
        Author
        Hu, H.
        Metadata
        Show full item record
        Summary
        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.
        URI
        https://studenttheses.uu.nl/handle/20.500.12932/20503
        Collections
        • Theses
        Utrecht university logo