2026-07-22T06:36:44Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:6040 2024-03-06T10:37:30Z ddc:004 open_access

Extension Complexity, MSO Logic, and Treewidth Kolman, Petr Koutecký, Martin Tiwary, Hans Raj Extension Complexity FPT Courcelle's Theorem MSO Logic We consider the convex hull P_phi(G) of all satisfying assignments of a given MSO_2 formula phi on a given graph G. We show that there exists an extended formulation of the polytope P_phi(G) that can be described by f(|phi|,tau)*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 phi and tau. In other words, we prove that the extension complexity of P_phi(G) is linear in the size of the graph G, with a constant depending on the treewidth of G and the formula phi. 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Petr Kolman and Martin Koutecký and Hans Raj Tiwary 2016 Is Part Of LIPIcs, Volume 53, 15th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2016) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.SWAT.2016.18 urn:nbn:de:0030-drops-60405 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SWAT.2016.18 eng https://creativecommons.org/licenses/by/3.0/legalcode