Petr Kolman ; Martin Koutecký ; Hans Raj Tiwary - Extension Complexity, MSO Logic, and Treewidth

dmtcs:5583 - Discrete Mathematics & Theoretical Computer Science, October 1, 2020, vol. 22 no. 4 - https://doi.org/10.23638/DMTCS-22-4-8
Extension Complexity, MSO Logic, and TreewidthArticle

Authors: Petr Kolman ; Martin Koutecký ; Hans Raj Tiwary

    We consider the convex hull $P_{\varphi}(G)$ of all satisfying assignments of a given MSO formula $\varphi$ on a given graph $G$. We show that there exists an extended formulation of the polytope $P_{\varphi}(G)$ that can be described by $f(|\varphi|,\tau)\cdot n$ inequalities, where $n$ is the number of vertices in $G$, $\tau$ is the treewidth of $G$ and $f$ is a computable function depending only on $\varphi$ and $\tau.$ In other words, we prove that the extension complexity of $P_{\varphi}(G)$ is linear in the size of the graph $G$, with a constant depending on the treewidth of $G$ and the formula $\varphi$. This provides a very general yet very simple meta-theorem about the extension complexity of polytopes related to a wide class of problems and graphs. As a corollary of our main result, we obtain an analogous result % for the weaker MSO$_1$ logic on the wider class of graphs of bounded cliquewidth. Furthermore, we study our main geometric tool which we term the glued product of polytopes. While the glued product of polytopes has been known since the '90s, we are the first to show that it preserves decomposability and boundedness of treewidth of the constraint matrix. This implies that our extension of $P_\varphi(G)$ is decomposable and has a constraint matrix of bounded treewidth; so far only few classes of polytopes are known to be decomposable. These properties make our extension useful in the construction of algorithms.


    Volume: vol. 22 no. 4
    Section: Discrete Algorithms
    Published on: October 1, 2020
    Accepted on: September 15, 2020
    Submitted on: June 18, 2019
    Keywords: Computer Science - Data Structures and Algorithms,Computer Science - Computational Complexity

    Consultation statistics

    This page has been seen 947 times.
    This article's PDF has been downloaded 357 times.