Extension Complexity, MSO Logic, and Treewidth
The result's identifiers
Result code in IS VaVaI
<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216208%3A11320%2F16%3A10331873" target="_blank" >RIV/00216208:11320/16:10331873 - isvavai.cz</a>
Result on the web
<a href="http://drops.dagstuhl.de/opus/volltexte/2016/6040/pdf/LIPIcs-SWAT-2016-18.pdf" target="_blank" >http://drops.dagstuhl.de/opus/volltexte/2016/6040/pdf/LIPIcs-SWAT-2016-18.pdf</a>
DOI - Digital Object Identifier
<a href="http://dx.doi.org/10.4230/LIPIcs.SWAT.2016.18" target="_blank" >10.4230/LIPIcs.SWAT.2016.18</a>
Alternative languages
Result language
angličtina
Original language name
Extension Complexity, MSO Logic, and Treewidth
Original language description
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.
Czech name
—
Czech description
—
Classification
Type
D - Article in proceedings
CEP classification
IN - Informatics
OECD FORD branch
—
Result continuities
Project
<a href="/en/project/GA15-11559S" target="_blank" >GA15-11559S: Extended Formulation of Polytopes</a><br>
Continuities
P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)
Others
Publication year
2016
Confidentiality
S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů
Data specific for result type
Article name in the collection
15th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2016)
ISBN
978-3-95977-011-8
ISSN
1868-8969
e-ISSN
—
Number of pages
14
Pages from-to
1-14
Publisher name
Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik
Place of publication
Dagstuhl, Germany
Event location
Reykjavik, Iceland
Event date
Jun 22, 2016
Type of event by nationality
WRD - Celosvětová akce
UT code for WoS article
—