Publication at Faculty of Mathematics and Physics |
2016
Abstract
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.