Abstrakt
We consider the convex hull Pφ(G) of all satisfying assignments of a given MSO formula φ on a given graph G. We show that there exists an extended formulation of the polytope Pφ(G) that can be described by f(|φ|,τ) n inequalities, where n is the number of vertices in G, τ is the treewidth of G and f is a computable function depending only on φ and τ.