Extension Complexity, MSO Logic, and Treewidth

Kód výsledku v 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>

Výsledek na webu

<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>

Jazyk výsledku

angličtina

Název v původním jazyce

Extension Complexity, MSO Logic, and Treewidth

Popis výsledku v původním jazyce

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.

Název v anglickém jazyce

Extension Complexity, MSO Logic, and Treewidth

Popis výsledku anglicky

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.

Druh

D - Stať ve sborníku

CEP obor

IN - Informatika

OECD FORD obor

—

Projekt

<a href="/cs/project/GA15-11559S" target="_blank" >GA15-11559S: Rozšířené formulace polytopů</a><br>

Návaznosti

P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)

Rok uplatnění

2016

Kód důvěrnosti údajů

S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

Název statě ve sborníku

15th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2016)

ISBN

978-3-95977-011-8

ISSN

1868-8969

e-ISSN

—

Počet stran výsledku

14

Strana od-do

1-14

Název nakladatele

Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik

Místo vydání

Dagstuhl, Germany

Místo konání akce

Reykjavik, Iceland

Datum konání akce

22. 6. 2016

Typ akce podle státní příslušnosti

WRD - Celosvětová akce

Kód UT WoS článku

—