文章基本信息

标题：Extension Complexity, MSO Logic, and Treewidth
本地全文：下载
作者：Petr Kolman ; Martin Kouteck{\'y ; Hans Raj Tiwary 等
期刊名称：LIPIcs : Leibniz International Proceedings in Informatics
电子版ISSN：1868-8969
出版年度：2016
卷号：53
页码：18:1-18:14
DOI：10.4230/LIPIcs.SWAT.2016.18
出版社：Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik
摘要：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.
关键词：Extension Complexity; FPT; Courcelle's Theorem; MSO Logic