Extension Complexity, MSO Logic, and TreewidthI
Petr Kolman, Martin Koutecký, Hans Raj Tiwary
Department of Applied Mathematics (KAM) &
Institute of Theoretical Computer Science (ITI),
Faculty of Mathematics and Physics (MFF),
Charles University in Prague, Czech Republic.

arXiv:1507.04907v6 [cs.DS] 11 May 2017

Abstract
We consider the convex hull Pϕ (G) of all satisfying assignments of a given MSO2 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 τ.
In other words, we prove that the extension complexity of Pϕ (G) is linear in the size of the graph
G, with a constant depending on the treewidth of G and the formula ϕ. 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.
Furthermore, we study our main geometric tool which we term the glued product of polytopes. Using
the results we obtain, we are able to show that our extension of Pϕ (G) is decomposable and has bounded
treewidth.
Keywords: Extension Complexity, FPT, Courcelle’s Theorem, MSO Logic

1. Introduction
In the ’70s and ’80s, it was repeatedly observed that various NP-hard problems are solvable in
polynomial time on graphs resembling trees. The graph property of resembling a tree was eventually
formalized as having bounded treewidth, and in the beginning of the ’90s, the class of problems efficiently
solvable on graphs of bounded treewidth was shown to contain the class of problems definable by the
Monadic Second Order Logic (MSO2 ) (Courcelle [12], Arnborg et al. [1], Courcelle and Mosbah [14]).
Using similar techniques, analogous results for weaker logics were then proven for wider graph classes
such as graphs of bounded cliquewidth and rankwidth [13]. Results of this kind are usually referred to as
Courcelle’s theorem for a specific class of structures.
In this paper we study the class of problems definable by the MSO logic from the perspective of
extension complexity. While small extended formulations are known for various special classes of polytopes,
we are not aware of any other result in the theory of extended formulations that works on a wide class of
polytopes the way Courcelle’s theorem works for a wide class of problems and graphs.
Our Contribution. We prove that satisfying assignments of an MSO2 formula ϕ on a graph of bounded
treewidth can be expressed by a “small” linear program. More precisely, there exists a computable function
f such that the convex hull – Pϕ (G) – of satisfying assignments of ϕ on a graph G on n vertices with
treewidth τ can be obtained as the projection of a polytope described by f (|ϕ|, τ ) · n linear inequalities;
we call Pϕ (G) the MSO polytope. All our results can be extended to general finite structures where the
restriction on treewidth applies to the treewidth of their Gaifman graph [35].
Our proof essentially works by “merging the common wisdom” from the areas of extended formulations
and fixed parameter tractability. It is known that dynamic programming can usually be turned into
I Preliminary version of this paper appeared at the 15th Scandinavian Symposium and Workshops on Algorithm Theory
(SWAT 2016).
This research was partially supported by projects GA15-11559S of GA ČR and 338216 of GA UK.
Email addresses: kolman@kam.mff.cuni.cz (Petr Kolman), koutecky@kam.mff.cuni.cz (Martin Koutecký),
hansraj@kam.mff.cuni.cz (Hans Raj Tiwary)

Preprint submitted to arXiv

May 17, 2017

a compact extended formulation [37, 22], and that Courcelle’s theorem can be seen as an instance of
dynamic programming [31], and therefore it should be expected that the polytope of satisfying assignments
of an MSO formula of a bounded treewidth graph be small.
However, there are a few roadblocks in trying to merge these two folklore wisdoms. For one, while
Courcelle’s theorem being an instance of dynamic programming in some sense may be obvious to an
FPT theorist, it is far from clear to anyone else what that sentence may even mean. On the other hand,
being able to turn a dynamic program into a compact polytope may be a theoretical possibility for an
expert on extended formulations, but it is by no means an easy statement for an outsider to comprehend.
What complicates the matters even further is that the result of Martin et al. [37] is not a result that
can be used in a black box fashion. That is, a certain condition must be satisfied to get a compact
extended formulation out of a dynamic program. This is far from a trivial task, especially for a theorem
like Courcelle’s theorem.
The main geometric tool we use is what we term the glued product of polytopes. We study this
operation and show that in a particular special case it behaves well with respect to the extension
complexity of polytopes, their decomposability and treewidth. That, in turn, allows us to prove more
about the structure of Pϕ (G).
The rest of the article is organized as follows. In Section 2 we review some previous work related to
Courcelle’s theorem and extended formulations. In Section 3 we describe the relevant notions related to
polytopes, extended formulations, graphs, treewidth and MSO logic. In Section 4 we study the several
properties of the glued product of polytopes. In Section 5 we prove the existence of compact extended
formulations for MSO polytopes parameterized by the length of the given MSO formula and the treewidth
of the given graph. In Section 6 we describe how to efficiently construct such a polytope given a tree
decomposition of a graph and apply our findings from Section 4. Finally, in Section 7, we prove additional
properties of Pϕ (G), show applicability of our proof to graphs of bounded cliquewidth, and obtain an
optimization version of Courcelle’s theorem in a particularly simple waye.
2. Related Work
2.1. MSO Logic vs. Treewidth
Because of the wide relevance of the treewidth parameter in many areas (cf. survey by Bodlaender [6])
and the large expressivity of the MSO and its extensions (cf. the survey of Langer et al. [32]), considerable
attention was given to Courcelle’s theorem by theorists from various fields, reinterpreting it into their
own setting. These reinterpretations helped uncover several interesting connections.
The classical way of proving Courcelle’s theorem is constructing a tree automaton A in time only
dependent on ϕ and the treewidth τ , such that A accepts a tree decomposition of a graph of treewidth τ
if and only if the corresponding graph satisfies ϕ; this is the automata theory perspective [12]. Another
perspective comes from finite model theory where one can prove that a certain equivalence on the set
of graphs of treewidth at most τ has only finitely many (depending on ϕ and τ ) equivalence classes
and that it behaves well [19]. Another approach proves that a quite different equivalence on so-called
extended model checking games has finitely many equivalence classes [27] as well; this is the game-theoretic
perspective. It can be observed that the finiteness in either perspective stems from the same roots.
Another related result is an expressivity result: Gottlob et al. [19] prove that on bounded treewidth
graphs, a certain subset of the database query language Datalog has the same expressive power as the
MSO. This provides an interesting connection between automata theory and database theory.
2.2. Extended Formulations
Sellmann, Mercier, and Leventhal [40] claimed to show compact extended formulation for binary
Constraint Satisfaction Problems (CSP) for graphs of bounded treewidth, but their proof is not correct [39].
The first two authors of this paper gave extended formulations for CSP that has polynomial size for
instances whose constraint graph has bounded treewidth [30] using a different technique. Bienstock and
Munoz [4] prove similar results for the approximate and exact version of the problem. In the exact case,
Bienstock and Munoz’s bounds are slightly worse than those of Kolman and Koutecký [30]. It is worth
noting that CSPs are a restricted subclass of problems that can be modeled using MSO logic. Laurent [33]
provides extended formulations for the independent set and max cut polytopes of size O(2τ n) for n-vertex
2

graphs of treewidth τ and, independently, Buchanan and Butenko [9] provide an extended formulation
for the independent set polytope of the same size.
A lot of recent work on extended formulations has focussed on establishing lower bounds in various
settings: exact, approximate, linear vs. semidefinite, etc. (See for example [16, 2, 7, 34]). A wide variety
of tools have been developed and used for these results including connections to nonnegative matrix
factorizations [43], communication complexity [15], information theory [8], and quantum communication
[16] among others.
For proving upper bounds on extended formulations, several authors have proposed various tools as
well. Kaibel and Loos [23] describe a setting of branched polyhedral systems which was later used by
Kaibel and Pashkovich [24] to provide a way to construct polytopes using reflection relations.
A particularly specific composition rule, which we term glued product (cf. Section 4), was studied by
Margot in his PhD thesis [36]. Margot showed that a property called the projected face property suffices
to glue two polytopes efficiently. Conforti and Pashkovich [11] describe and strengthen Margot’s result to
make the projected face property to be a necessary and sufficient condition to describe the glued product
in a particularly efficient way.
Martin et al. [37] have shown that under certain conditions, an efficient dynamic programming based
algorithm can be turned into a compact extended formulation. Kaibel [22] summarizes this and various
other methods.
3. Preliminaries
3.1. Polytopes, Extended Formulations and Extension Complexity
For background on polytopes we refer the reader to Grünbaum [20] and Ziegler [44]. To simplify
reading of the paper for audience not working often in the area of polyhedral combinatorics, we provide
here a brief glossary of common polyhedral notions that are used in this article.
A hyperplane in Rn is a closed convex set of the form {x|a| x = b} where a ∈ Rn , b ∈ R. A halfspace
in Rn is a closed convex set of the form {x|a| x 6 b} where a ∈ Rn , b ∈ R. The inequality a| x 6 b is said
to define the corresponding halfspace. A polytope P ⊆ Rn is a bounded subset defined by intersection
of finite number of halfspaces. A result of Minkowsky-Weyl states that equivalently, every polytope is
the convex hull of a finite number of points. Let h be a halfspace defined by an inequality a| x 6 b; the
inequality is said to be valid for a polytope P if P = P ∩ h. Let a| x 6 b be a valid inequality for polytope
P ; then, P ∩ {x|a| x = b} is said to be a face of P . For a vector x ∈ Rn , we use x[i] to denote its i-th
coordinate.
Note that, taking a to be the zero vector and b = 0 results in the face being P itself. Also, taking a to
be the zero vector and b = 1 results in the empty set. These two faces are often called the trivial faces
and they are polytopes “living in” dimensions n and −1, respectively. Every face – that is not trivial – is
itself a polytope of dimension d where 0 6 d 6 n − 1.
It is not uncommon to refer to three separate (but related) objects as a face: the actual face as defined
above, the valid inequality defining it, and the equation corresponding to the valid inequality. While this
is clearly a misuse of notation, the context usually makes it clear as to exactly which object is being
referred to.
The zero dimensional faces of a polytope are called its vertices, and the (n − 1)-dimensional faces are
called its facets.
Let P be a polytope in Rd . A polytope Q in Rd+r is called an extended formulation or an extension of
P if P is a projection of Q onto the first d coordinates. Note that for any linear map π : Rd+r → Rd such
that P = π(Q), a polytope Q0 exists such that P is obtained by dropping all but the first d coordinates
on Q0 and, moreover, Q and Q0 have the same number of facets.
The size of a polytope is defined to be the number of its facet-defining inequalities. Finally, the
extension complexity of a polytope P , denoted by xc(P ), is the size of its smallest extended formulation.
We refer the readers to the surveys [10, 41, 22, 42] for details and background of the subject and we only
state two basic propositions about extended formulations here.
Proposition 1. Let P be a polytope with a vertex set V = {v1 , . . . , vn }. Then xc(P ) 6 n.

3

Proof. Let P = conv ({v1 , . . . , vn }) be a polytope. Then, P is the projection of
(
)
n
n
X
X
Q = (x, λ) x =
λi vi ;
λi = 1; λi > 0 for i ∈ {1, . . . , n} .
i=1

i=1

It is clear that Q has at most n facets and therefore xc(P ) 6 n.
Proposition 2. Let P be a polytope obtained by intersecting a set H of hyperplanes with a polytope Q.
Then xc(P ) 6 xc(Q).
Proof. Note that any extended formulation of Q, when intersected with H, gives an extended formulation
of P . Intersecting a polytope with hyperplanes does not increase the number of facet-defining inequalities
(and only possibly reduces it).
3.2. Graphs and Treewidth
For notions related to the treewidth of a graph and nice tree decomposition, in most cases we stick to
the standard terminology as given in the book by Kloks [26]; the only deviation is in the leaf nodes of
the nice tree decomposition where we assume that the bags are empty. For a vertex v ∈ V of a graph
G = (V, E), we denote by δG (v) the set of neighbors of v in G, that is, δG (v) = {u ∈ V | {u, v} ∈ E}. If
the graph G is clear from the context, we omit the subscript and simply write δ(v).
A tree decomposition of a graph G = (V, E) is a pair (T, B), where T is a rooted tree and B is a
mapping B : V (T ) → 2V satisfying
• for any uv ∈ E, there exists a ∈ V (T ) such that u, v ∈ B(a),

• if v ∈ B(a) and v ∈ B(b), then v ∈ B(c) for all c on the path from a to b in T .
We use the convention that the vertices of the tree are called nodes and the sets B(a) are called bags.
Occasionally, we will view the mapping B as the set B = {B(u) | u ∈ V }.
The treewidth tw((T, B)) of a tree decomposition (T, B) is the size of the largest bag of (T, B) minus
one. The treewidth tw(G) of a graph G is the minimum treewidth over all possible tree decompositions of
G.
A nice tree decomposition is a tree decomposition with one special node r called the root in which
each node is one of the following types:
• Leaf node: a leaf a of T with B(a) = ∅.

• Introduce node: an internal node a of T with one child b for which B(a) = B(b) ∪ {v} for some
v ∈ B(a).

• Forget node: an internal node a of T with one child b for which B(a) = B(b) \ {v} for some v ∈ B(b).
• Join node: an internal node a with two children b and c with B(a) = B(b) = B(c).

For a vertex v ∈ V , we denote by top(v) the topmost node of the nice tree decomposition (T, B) that
contains v in its bag. For any graph G of treewith τ on n vertices, a nice tree decomposition of G of
width τ with at most 8n nodes can be computed in time f (τ ) · n, for some computable function f [5, 26].
Given a graph G = (V, E) and a subset of vertices {v1 , . . . , vd } ⊆ V , we denote by G[v1 , . . . , vd ] the
subgraph of G induced by the vertices v1 , . . . , vd . Given a tree decomposition (T, B) and a node a ∈ V (T ),
we denote by Ta the subtreeSof T rooted in a, and by Ga the subgraph of G induced by all vertices in
bags of Ta , that is, Ga = G[ b∈V (Ta ) B(b)]. Throughout this paper we assume that for every graph, its
vertex set is a subset of N. We define the following operator η: for any set U = {v1 , v2 , . . . , vl } ⊆ N,
η(U ) = (vi1 , vi2 , . . . , vil ) such that vi1 < vi2 · · · < vil .
~ ) where G = (V, E) is a graph and
For an integer m ≥ 0, an [m]-colored graph is a pair (G, V
~
V = (V1 , . . . , Vm ) is an m-tuple of subsets of vertices of G called an m-coloring of G. For integers m ≥ 0
~ , p~) where (G, V
~ ) is an [m]-colored graph
and τ ≥ 0, an [m]-colored τ -boundaried graph is a triple (G, V
~ and p~ are clear
and p~ = (p1 , . . . , pτ ) is a τ -tuple of vertices of G called a boundary of G. If the tuples V
from the context or if their content is not important, we simply denote an [m]-colored τ -boundaried graph
by G[m],τ . For a tuple p~ = (p1 , . . . , pτ ), we denote by p the corresponding set, that is, p = {p1 , . . . , pτ }.
4

p1

p2
p3

Figure 1: A [3]-colored 3-boundaried graph with p
~ = (p1 , p2 , p3 ).

~ , p~) and (G2 , U
~ , ~q) are compatible if the function h :
Two [m]-colored τ -boundaried graphs (G1 , V
p~ → ~q, defined by h(pi ) = qi for each i, is an isomorphism of the induced subgraphs G1 [p1 , . . . , pτ ] and
G2 [q1 , . . . , qτ ], and if for each i and j, pi ∈ Vj ⇔ qi ∈ Uj .

p1

q2

p2
p3

q1

q3

~ , ~q)
(G2, W

~ , p~)
(G1, U

Figure 2: Compatibility of two [3]-colored 3-boundaried graphs.
[m],τ
~ , p~) and G[m],τ = (G2 , W
~ , ~q),
Given two compatible [m]-colored τ -boundaried graphs G1
= (G1 , U
2
[m],τ
[m],τ
[m],τ
[m],τ
[m],τ
the join of G1
and G2
, denoted by G1
⊕ G2
, is the [m]-colored τ -boundaried graph G
=
~ , p~) where
(G, V

• G is the graph obtained by taking the disjoint union of G1 and G2 , and for each i, identifying the
vertex pi with the vertex qi and keeping the label pi for it;
~ = (V1 , . . . , Vm ) with Vj = Uj ∪ Wj and every qi replaced by pi , for each j and i;
• V

• p~ = (p1 , . . . , pτ ) with pi being the node in V (G) obtained by the identification of pi ∈ V (G1 ) and
qi ∈ V (G2 ), for each i.
[m],τ

Because of the choice of referring to the boundary vertices by their names in G1
, it does not always
[m],τ
[m],τ
[m],τ
[m],τ
hold that G1
⊕ G2
= G2
⊕ G1
; however, the two structures are isomorphic and equivalent
for our purposes (see below).

p1

q2

p2
p3

q1

p1

q3

⊕
~ , p~)
(G1, U

p2
p3

=

~ , ~q)
(G2, W

~ , p~) ⊕ (G2, W
~ , ~q)
(G1, U

Figure 3: The join of two [m]-colored τ -boundaried graphs.

5

3.3. Monadic Second Order Logic and Types of Graphs
In most cases, we stick to standard notation as given by Libkin [35]. A vocabulary σ is a finite collection
of constant symbols c1 , c2 , . . . and relation symbols P1 , P2 , . . .. Each relation symbol Pi has an associated
A
arity ri . A σ-structure is a tuple A = (A, {cA
i }, {Pi }) that consists of a universe A together with an
interpretation of the constant and relation symbols: each constant symbol ci from σ is associated with an
A
ri
element cA
i ∈ A and each relation symbol Pi from σ is associated with an ri -ary relation Pi ⊆ A .
To give an example, a graph G = (V, E) can be viewed as a σ1 -structure (V, ∅, {E}) where E is a
symmetric binary relation on V ×V and the vocabulary σ1 contains a single relation symbol. Alternatively,
for another vocabulary σ2 containing three relation symbols, one of arity two and two of arity one, one
can view a graph G = (V, E) also as a σ2 -structure I(G) = (VI , ∅, {EI , LV , LE }), with VI = V ∪ E,
EI = {{v, e} | v ∈ e, e ∈ E}, LV = V and LE = E; we will call I(G) the incidence graph of G. In our
approach we will make use of the well known fact that the treewidths of G and I(G), viewed as a σ1 - and
σ2 - structures as explained above, differ by at most one [29].
The main subject of this paper are formulas for graphs in monadic second order logic (MSO) which
is an extension of first order logic that allows quantification over monadic predicates (i.e., over sets of
vertices). By MSO2 we denote the extension of MSO that allows in addition quantification over sets of
edges. As every MSO2 formula ϕ over σ1 can be turned into an MSO1 formula ϕ0 over σ2 such that for
every graph G, G |= ϕ if and only if I(G) |= ϕ0 [folklore], for the sake of presentation we restrict our
attention, without loss of generality, to MSO1 formulae over the σ2 vocabulary. To further simplify the
presentation, without loss of generality (cf. [25]) we assume that the input formulae are given in a variant
of MSO1 that uses only set variables (and no element variables).
An important kind of structures that are necessary in the proofs in this paper are the [m]-colored τ boundaried graphs. An [m]-colored τ -boundaried graph G = (V, E) with boundary p1 , . . . , pτ colored with
V1 , . . . , Vm is viewed as a structure (VI , {p1 , . . . , pτ }, {EI , LV , LE , V1 , . . . , Vm }); for notational simplicity,
~ , p~). The corresponding vocabulary is denoted by σm,τ .
we stick to the notation G[m],τ or (G, V
~ is the tuple of all
A variable X is free in ϕ if it does not appear in any quantification in ϕ. If X
~ A variable X is bound in ϕ if it is not free. By qr(ϕ) we denote
free variables in ϕ, we write ϕ(X).
the quantifier rank of ϕ which is the number of quantifiers of ϕ when transformed into the prenex form
(i.e., all quantifiers are at the beginning of the formula). We denote by MSO[k, τ, m] the set of all MSO1
formulae ϕ over the vocabulary στ,m with qr(ϕ) ≤ k.
[m],τ
[m],τ
Two [m]-colored τ -boundaried graphs G1
and G2
are MSO[k ]-elementarily equivalent if they
[m],τ
[m],τ
SO
satisfy the same MSO[k, τ, m] formulae; this is denoted by G1
≡M
G2
. The main tool in the
k
model theoretic approach to Courcelle’s theorem, that will also play a crucial role in our approach, can
be stated as the following theorem which follows from [35, Proposition 7.5 and Theorem 7.7].
SO
Theorem 1 ([35]). For any fixed τ, k, m ∈ N, the equivalence relation ≡M
has a finite number of
k
equivalence classes.
SO
Let us denote the equivalence classes of the relation ≡M
by C = {α1 . . . , αw }, fixing an ordering
k
such that α1 is the class containing the empty graph. Note that the size of C depends only on k, m and
τ , that is, |C| = f (k, m, τ ) for some computable function f . For a given MSO formula ϕ with m free
variables, we define an indicator function ρϕ : {1, . . . , |C|} → {0, 1} as follows: for every i, if there exists a
graph G[m],τ ∈ αi such that G[m],τ |= ϕ, we set ρϕ (i) = 1, and we set ρϕ (i) = 0 otherwise; note that if
there exists a graph G[m],τ ∈ αi such that G[m],τ |= ϕ, then G0[m],τ |= ϕ for every G0[m],τ ∈ αi .
SO
For every [m]-colored τ -boundaried graph G[m],τ , its type, with respect to the relation ≡M
, is the
k
[m],τ
class to which G
belongs. We say that types αi and αj are compatible if there exist two [m]-colored
τ -boundaried graphs of types αi and αj that are compatible; note that this is well defined as all [m]-colored
τ -boundaried graphs of a given type are compatible. For every i ≥ 1, we will encode the type αi naturally
as a binary vector {0, 1}|C| with exactly one 1, namely with 1 on the position i.
An important property of the types and the join operation is that the type of a join of two [m]-colored
τ -boundaried graphs depends on their types only.
[m],τ

[m],τ

[m],τ

[m],τ

Lemma 1 ([35, Lemma 7.11] and [19, Lemma 3.5]). Let Ga , Ga0 , Gb
and Gb0
be [m]-colored τ [m],τ
[m],τ
[m],τ
[m],τ
[m],τ
[m],τ
M SO
M SO
SO
boundaried graphs such that Ga
≡k
Ga0
and Gb
≡k
Gb0 . Then (Ga
⊕ Gb
) ≡M
k
[m],τ
[m],τ
(Ga0 ⊕ Gb0 ).
6

The importance of the lemma rests in the fact that for determination of the type of a join of two
[m]-colored τ -boundaried graphs, it suffices to know only a small amount of information about the two
graphs, namely their types. The following two lemmas deal in a similar way with the type of a graph in
other situations.
~ p~), (Gb , Y
~ , ~q) be [m]-colored τ -boundaried graphs and let (Ga0 , X
~ 0 , p~0 ),
Lemma 2 ([19, implicit]). Let (Ga , X,
0
0
0
0
(Gb0 , Y~ , q~ ) be [m]-colored (τ + 1)-boundaried graphs with Ga = (V, E), Ga0 = (V , E ), Gb = (W, F ),
Gb0 = (W 0 , F 0 ) such that
~ p~) ≡M SO (Gb , Y
~ , ~q);
1. (Ga , X,
k

~ 0 [V ], p~0 [V ]) = (Ga , X,
~ p~);
2. V 0 = V ∪ {v} for some v 6∈ V , δ(v) ⊆ p, p~ is a subtuple of p~0 and (Ga0 [V ], X
3. W 0 = W ∪ {w} for some w 6∈ W , δ(w) ⊆ q, ~q is a subtuple of q~0 and (Gb0 [W ], Y~ 0 [W ], q~0 [W ]) =
~ , ~q);
(Gb , Y
~ 0 , p~0 ) and (Gb0 , Y~ 0 , q~0 ) are compatible.
4. (Ga0 , X
~ 0 , p~0 ) ≡M SO (Gb0 , Y~ 0 , q~0 ).
Then (Ga0 , X
k
~ p~), (Gb , Y
~ , ~q) be [m]-colored τ -boundaried graphs and let (Ga0 , X
~ 0 , p~0 ),
Lemma 3 ([19, implicit]). Let (Ga , X,
0
0
0
0
~
~
0
0
(Gb , Y , q ) be [m]-colored (τ + 1)-boundaried graphs with Ga = (V, E), Ga = (V , E ), Gb = (W, F ),
Gb0 = (W 0 , F 0 ) such that
~ 0 , p~0 ) ≡M SO (Gb0 , Y~ 0 , q~0 );
1. (Ga0 , X
k

~ 0 [V ], p~0 [V ]) = (Ga , X,
~ p~);
2. V ⊆ V 0 , |V 0 | = |V | + 1, p~ is a subtuple of p~0 and (Ga0 [V ], X
~ , ~q).
3. W ⊆ W 0 , |W 0 | = |W | + 1, ~q is a subtuple of q~0 and (Gb0 [W ], Y~ 0 [W ], q~0 [W ]) = (Gb , Y
~ p~) ≡M SO (Gb , Y
~ , ~q).
Then (Ga , X,
k
3.4. Feasible Types
Suppose that we are given an MSO1 formula ϕ over σ2 with m free variables and a quantifier rank at
most k, a graph G of treewidth at most τ , and a nice tree decomposition (T, B) of the graph G.
For every node of T we are going to define certain types and tuples of types as feasible. For a node
b ∈ V (T ) of any kind (leaf, introduce, forget, join) and for α ∈ C, we say that α is a feasible type of the node
~ = (X1 , . . . , Xm );
~ η(B(b))) is of type α where X
b if there exist X1 , . . . , Xm ⊆ V (Gb ) such that (Gb , X,
~
we say that X realizes type α on the node b. We denote the set of feasible types of the node b by F(b).
For an introduce node b ∈ V (T ) with a child a ∈ V (T ) (assuming that v is the new vertex), for
~ = (X1 , . . . , Xm )
α ∈ F(a) and β ∈ F(b), we say that (α, β) is a feasible pair of types for b if there exist X
0
0
0
~
and X = (X1 , . . . , Xm ) realizing types α and β on the nodes a and b, respectively, such that for each i,
either Xi0 = Xi or Xi0 = Xi ∪ {v}. We denote the set of feasible pairs of types of the introduce node b by
Fp (b).
For a forget node b ∈ V (T ) with a child a ∈ V (T ) and for β ∈ F(b) and α ∈ F(a), we say (α, β) is a
~ realizing β on b and α on a. We denote the set of feasible
feasible pair of types for b if there exists X
pairs of types of the forget node b by Fp (b).
For a join node c ∈ V (T ) with children a, b ∈ V (T ) and for α ∈ F(c), γ1 ∈ F(a) and γ2 ∈ F(b), we
say that (γ1 , γ2 , α) is a feasible triple of types for c if γ1 , γ2 and α are mutually compatible and there exist
1
2
~ = (X 1 ∪ X 2 , . . . , Xm
X~ 1 , X~ 2 realizing γ1 and γ2 on a and b, respectively, such that X
∪ Xm
) realizes α
1
1
on c. We denote the set of feasible triples of types of the join node c by Ft (c).
We define an indicator function ν : C × V (T ) × V (G) × {1, . . . , m} → {0, 1} such that ν(β, b, v, i) = 1
~ = (X1 , . . . , Xm ) realizing the type β on the node b ∈ V (T ) with v ∈ B(b) and
if and only if there exists X
v ∈ Xi . Additionally, we define µ : C × V (G) × {1, . . . , m} → {0, 1} to be µ(β, v, i) = ν(β, top(v), v, i).

7

4. Glued product of Polytopes over Common Coordinates
The (cartesian) product of two polytopes P1 and P2 is defined as
P1 × P2 = conv ({(x, y) | x ∈ P1 , y ∈ P2 }) .
Proposition 3. Let P1 , P2 be two polytopes. Then
xc(P1 × P2 ) 6 xc(P1 ) + xc(P2 ) .
Proof. Let Q1 and Q2 be extended formulations of P1 and P2 , respectively. Then, Q1 × Q2 is an extended
formulation of P1 × P2 . Now assume that Q1 = {x | Ax 6 b} and Q2 = {y | Cy 6 d} and that these are
the smallest extended formulations of P1 and P2 , resp. Then,
Q1 × Q2 = {(x, y) | Ax 6 b, Cy 6 d} .
That is, we have an extended formulation of P1 × P2 of size at most xc(P1 ) + xc(P2 ).
We are going to define the glued product of polytopes, a slight generalization of the usual product
of polytopes. We study a case where the extension complexity of the glued product of two polytopes is
upper bounded by the sum of the extension complexities of the two polytopes and which exhibits several
other nice properties. Then we use it in Section 5 to describe a small extended formulation for the MSO
polytope Pϕ (G) on graphs with bounded treewidth.
Let P ⊆ Rd1 +k and Q ⊆ Rd2 +k be 0/1-polytopes defined by m1 and m2 inequalities and with vertex
sets vert(P ) and vert(Q), respectively. Let IP ⊆ {1, . . . , d1 + k} be a subset of coordinates of size k,
IQ ⊆ {1, . . . , d2 + k} be a subset of coordinates of size k, and let IP0 = {1, . . . , d1 + k} \ IP . For a vector
x, and a subset I of coordinates, we denote by x|I the subvector of x specified by the coordinates I. The
glued product of P and Q, (glued) with respect to the k coordinates IP and IQ , denoted by P ×k Q, is
defined as


P ×k Q = conv (x|IP0 , y) ∈ Rd1 +d2 +k | x ∈ vert(P ), y ∈ vert(Q), x|IP = y|IQ .
We adopt the following convention while discussing glued products in the rest of this article. In the
above scenario, we say that P ×k Q is obtained by gluing P and Q along the k coordinates IP of P with
the k coordinates IQ of Q. If, for example, these coordinates are named z in P and w in Q, then we also
say that P and Q have been glued along the z and w coordinates and we refer to the coordinates z and
w as the glued coordinates. In the special case that we glue along the last k coordinates, the definition of
the glued product simplifies to


P ×k Q = conv (x, y, z) ∈ Rd1 +d2 +k | (x, z) ∈ vert(P ), (y, z) ∈ vert(Q) .
This notion was studied by Margot [36] who provided a sufficient condition for being able to write
the glued product in a specific (and efficient) way from the descriptions of P and Q. We will use this
particular way in Lemma 4. The existing work [36, 11], however, is more focused on characterizing exactly
when this particular method works. We do not need the result in its full generality and therefore we only
state a very specific version of it that is relevant for our purposes; for the sake of completeness, we also
provide a proof of it.
Lemma 4 (Gluing lemma). Let P and Q be 0/1-polytopes and let the k (glued) coordinates in P be
labeled z1 , . . . , zk , and the k (glued) coordinates in Q be labeled w1 , . . . , wk . Suppose that 1| z 6 1 is valid
for P and 1| w 6 1 is valid for Q. Then xc(P ×k Q) 6 xc(P ) + xc(Q).

Proof. Let (x0 , z 0 , y 0 , w0 ) be a point from P ×Q∩{(x, z, y, w)|z = w}. Observe that the point (x0 , z 0 ) is a conPk
vex combination of points (x0 , 0), (x0 , e1 ), . . . , (x0 , ek ) from P with coefficients (1 − i=1 zi0 ), z10 , z20 , . . . , zk0
0
0
where ei is the i-th unit vector. Similarly, the point (y , w ) is a convex combination of points
Pk
(y 0 , 0), (y 0 , e1 ), . . . , (y 0 , ek ) from Q with coefficients (1 − i=1 wi0 ), w10 , w20 , . . . , wk0 . Notice that for every j ∈ {1, . . . , k}, (x0j , ej , yj0 ) is a point from the glued product. As wi = zi for every i ∈ {1, . . . , k}, we
conclude that (x0 , w0 , z 0 ) ∈ P ×k Q. Thus, by Proposition 2 the extension complexity of P ×k Q is at
most that of P × Q which is at most xc(P ) + xc(Q) by Proposition 3.
The results of the following subsections are needed in Section 7; they are not needed for results in
Sections 5 and 6.
8

4.1. Decomposability of Polyhedra
Now we will define decomposable polyhedra and show that decomposability is preserved by taking
glued product. Decomposability is also known as integer decomposition property or being integrally closed
in the literature (cf. Schrijver [38]). The best known example are polyhedra given by totally unimodular
matrices [3].
A polyhedron P ⊆ Rn is decomposable if for every r ∈ N and every x ∈ rP ∩ Zn , there exist
1
x , . . . , xr ∈ P ∩ Zn with x = x1 + · · · + xr , where rP = {ry | y ∈ P }. A decomposition oracle for a
decomposable P is one that, queried on r ∈ N and on x ∈ rP ∩ Zn , returns x1 , . . . , xr ∈ P ∩ Zn with
x = x1 + · · · + xr . If a decomposition oracle for P is realizable by an algorithm running in time polynomial
in the length of the unary encoding of r and x, we say that P is constructively decomposable.
Lemma 5 (Decomposability and glued product). Let P ⊆ Rd1 +k and Q ⊆ Rd2 +k be 0/1-polytopes and let
the k glued coordinates in P be labeled z1 , . . . , zk , and the k glued coordinates in Q be labeled w1 , . . . , wk .
Suppose that 1| z 6 1 is valid for P and 1| w 6 1 is valid for Q. Then if P and Q are constructively
decomposable, so is P ×k Q.
Proof. For the sake of simplicity, we assume without loss of generality that glueing is done along the last
k coordinates. Then P ×k Q = conv{(x, y, z) ∈ Rd1 +d2 +k | (x, z) ∈ vert(P ), (y, w) ∈ vert(Q), z = w}. Let
R = P ×k Q. To prove that R is constructively decomposable, it suffice to find, for every integer
Pr r ∈ N and
every integer vector (x, y, z) ∈ rR, r integer vectors (xi , y i , z i ) ∈ R such that (x, y, z) = i=1 (xi , y i , z i ).
Using the assumption that P and Q are constructively
decomposable, we find in polynomial time r
Pr
i i
i i
integer vectors
(x
,
z
)
∈
P
such
that
(x,
z)
=
(x
,
z
) and r integer vectors (y j , z̄ j ) ∈ Q such that
i=1
Pr
(y, z) = j=1 (y j , z̄ j ).
Pr
Pr
Observe that z = i=1 z i = j=1 z̄ j . Moreover, because z i and z̄ j satisfy 1| z i 6 1 and 1| z̄ j 6 1 for
all i and j, respectively, each vector z i and each vector z̄ j contains at most one 1. Clearly, the number of
vectors z i with zli = 1 is equal to the number of vectors z̄ j with z̄lj = 1, namely zl .
Thus, it is possible to greedily pair the vectors (xi , z i ) and (y j , z̄ j ) one to one in such a way that
i
z = z̄ j for all the paired vectors. By merging each such
Pr pair of vectors, we obtain r new integer vectors
(xl , y l , z l ) ∈ R, for 1 ≤ l ≤ r, that satisfy (x, y, z) = l=1 (xl , y l , z l ), concluding the proof.
The following lemma will be useful:
0

0

Lemma 6. Let Q ⊆ Rn be a polyhedron which is constructively decomposable, let π : Rn → Rn be a linear
projection with integer coefficients and let P = π(Q). Then the polytope R = conv({(y, π(y)) | y ∈ Q}) is
constructively decomposable.
Proof. Consider an integer r and an integer vector (x, y) ∈ rR. Since Q is constructively
Pr decomposable,
0
we can find in polynomial time r vectors y i ∈ Q ∩ Zn , for 1 ≤ i ≤ P
r, such thatP
y = i=1 y i . For every
i, let xi P
= π(y i ); note that every xi is integral. Since x = π(y) = i π(y i ) = i xi , we conclude that
r
(x, y) = i=1 ((xi , y i )), proving that R is constructively decomposable.
Obviously, not all integer polyhedra are decomposable: consider the three-dimensional parity polytope
P = conv({(0, 0, 0), (1, 1, 0), (1, 0, 1), (0, 1, 1)}) and the point (1, 1, 1) ∈ 2P – there is no way to express it
as a sum of integral points in P . However, the following lemma shows that every integer polyhedron has
an extension that is decomposable.
Lemma 7. Every 0/1 integer polytope P has an extension R that is constructively decomposable. Moreover,
a description of such an extension can be computed in time O(d + n) where d is the dimension of P and
n is the number of vertices of P if the vertices of P are given.
Pn
Proof. Let vert(P ) = {v1 , . . . , vn } denote all the vertices of P and let Q = {λ |
= 1, λi ≥
i=1 λi P
n
0 for i ∈ {1, . . . , n}} be the n-dimensional simplex. Then, for the linear projection π(λ) = i=1 λi vi ,
the polytope R = {(π(λ), λ) | λ ∈ Q} is an extended formulation of P (note that the same extended
formulation of P is used also in the proof of Proposition 1).
Pn
Consider an arbitraty integer r and an integral point x = (x1 , . . . , xn ) ∈ rQ. As x = j=1 xj ej where
Pn
ej is the j-the unit vector, and as j=1 xj = r, we see that x can be written as a sum of at most r
integral points from Q, and such a decomposition can be found in time polynomial in n and d. Thus,
Q is constructively decomposable. Then, applying the previous lemma to the simplex Q and the linear
projection π, we see that the polytope R is constructively decomposable.
9

Given a polytope P , it is an interesting problem to determine the minimum size of an extension of P
that is decomposable. This is an analogue of extension complexity: the decomposable extension complexity
of a polytope P , denoted xcdec (P ), is the minimum size of an extension of P that is decomposable. A
polytope Q which is an extension of P and is decomposable is called a decomposable extension of P .
Obviously, xc(P ) ≤ xcdec (P ). Using Lemma 6 and Proposition 1 we see that if a polytope P
has n vertices, then xcdec (P ) ≤ n. It is an interesting problem to determine for which polytopes
xc(P ) = xcdec (P ), or, on the other hand, when xc(P ) < xcdec (P ) and by how much they can differ.
4.2. Treewidth of Gaifman Graphs of Extended Formulations
Given a relational structure A = (A, S) where S ⊆ 2A , its Gaifman graph is the graph G(A) = (A, E)
where E = {{u, v} | ∃S ∈ S : u, v ∈ S}. The Gaifman graph G(A) associated with a matrix A ∈ Rm×n is
the Gaifman graph of the structure ({1, . . . , n}, {supp(ai ) | 1 ≤ i ≤ m}) where ai is the i-th row of A
and supp(x) is the support of a vector x, that is, the set of indices i such that xi 6= 0. In other words, the
graph G(A) has a vertex for each column of A and two vertices are connected by an edge if the supports
of the corresponding columns have non-empty intersection.
The treewidth of a matrix A ∈ Rn×m , denoted tw(A), is the treewidth of its Gaifman graph. The
treewidth of a system of inequalities Ax ≤ b is defined as tw(A).
Lemma 8 (Treewidth and glued product). Let P and Q be 0/1-polytopes and let the k glued coordinates in
P be labeled z1 , . . . , zk and the k glued coordinates in Q be labeled w1 , . . . , wk . Suppose that 1| z 6 1 is valid
for P and 1| w 6 1 is valid for Q. Let Ax+Cz ≥ a be inequalities describing an extended formulation of P
and Dw + Ey ≥ b be inequalities describing an extended formulation of Q. Then there exists an extended
formulation of P ×k Q described by inequalities F v ≥ c such that tw(F ) ≤ max{tw(A C), tw(D E), k}.
Moreover, if (TP , BP ) is a tree decomposition of G(A C) of treewidth tw(A C) with a node d with
“columns of C” ⊆ BP (d) and (TQ , BQ ) is a tree decomposition of G(D E) of treewidth tw(D E) containing
a node d0 with “columns of D” ⊇ BQ (d0 ), then we can choose F and c in such a way that a tree
decomposition (TR , BR ) of G(F ) of treewidth max{tw(A C), tw(D E), k} exists, where TR is obtained
from TP and TQ by identifying the nodes d and d0 and BR = BP ∪ (BQ \ {BQ (d0 )}).
Proof. We start by observing that the assumptions and the gluing lemma imply that the inequalities
≥a

Ax+Cz

Dz + Ey ≥ b


C 0 . The
describe an extended formulation of P ×k Q. Consider the treewidth of the matrix F = A0 D
E
Gaifman graph G(F ) of F can be obtained by taking G(A C) and G(D E) and identifying the vertices
corresponding to the variables z and w in the above formulation. It is easy to observe that the treewidth
of G(F ) is max(tw(P ), tw(Q), k), as desired, and that if (TP , BP ) and (TQ , BQ ) are as assumed, the tuple
(TR , BR ) obtained in the aforementioned way is indeed a tree decomposition of G(F ).
Lemma 9. Let P ⊆ Rm be a polytope with n vertices v1 , . . . , vn . Then there exist an extension of P that
can be described by inequalities of treewidth at most n + m.
Proof. Consider again the description of the extension of P used in the proof of Proposition 1:
1λ

=1

(1)

V λ − Ix = 0

(2)

≥0

λ

(3)

where 0 and 1 are the all-0 and all-1 vectors of appropriate dimensions, respectively, I is the identity
matrix and V is a matrix whose i-th column is vi (each equality is just an abbreviation of two opposing
inequalities). Since the number of columns in the system is n + m, its treewidth is by definition also at
most n + m.
Putting Lemmas 7 and 9 together gives the following corollary:

10

Corollary 1. Let P ⊆ Rm be an integral polytope with n vertices v1 , . . . , vn . Then there exist a
constructively decomposable extension of P that can be described by inequalities of treewidth at most
n + m.
Proof. It suffices to notice that the extended formulations of Lemmas 7 and 9 are identical and thus
simultaneously have small treewidth and are decomposable.
5. Extension Complexity of the MSO Polytope
~ over σ2 with m free set variables X1 , . . . , Xm , we define a polytope
For a given MSO1 formula ϕ(X)
of satisfying assignments on a given graph G, represented as a σ2 -structure I(G) = (VI , ∅, {EI , LV , LE })
with domain of size n, in a natural way. We encode any assignment of elements of I(G) to the sets
X1 , . . . , Xm as follows. For each Xi in ϕ and each v in VI , we introduce a binary variable yvi . We set yvi
to be one if v ∈ Xi and zero otherwise. For a given 0/1 vector y, we say that y satisfies ϕ if interpreting
the coordinates of y as described above yields a satisfying assignment for ϕ. The polytope of satisfying
assignments, also called the MSO polytope, is defined as
Pϕ (G) = conv ({y ∈ {0, 1}nm | y satisfies ϕ}) .
For the sake of simplicity, we state the following theorem and carry out the exposition for graphs;
however, identical arguments can be carried out analogously for any σ2 -structure whose Gaifman graph
has treewidth bounded by τ .
Theorem 2 (Extension Complexity of the MSO Polytope). For every graph G represented as I(G) and
for every MSO1 formula ϕ over σ2 , xc(Pϕ (G)) ≤ f (|ϕ|, τ ) · n where f is some computable function,
τ = tw(G) and n = |VI |.
Proof. Let (T, B) be a fixed nice tree decomposition of treewidth τ of I(G) and let k denote the quantifier
rank of ϕ and m the number of free variables of ϕ. Let C be the set of equivalence classes of the relation
SO
≡M
. For each node b of T we introduce |C| binary variables that will represent a feasible type of
k
the node b; we denote the vector of them by tb (i.e., tb ∈ {0, 1}|C| ). For each introduce and each forget
node b of T , we introduce additional |C| binary variables that will represent a feasible type of the child
(descendant) of b; we denote the vector of them by db (i.e., db ∈ {0, 1}|C| ). Similarly, for each join node b
we introduce additional |C| binary variables, denoted by lb , that will represent a feasible type of the left
child of b, and other |C| binary variables, denoted by rb , that will represent a feasible type of the right
child of b (i.e., lb , rb ∈ {0, 1}|C| ).
We are going to describe inductively a polytope in the dimension given (roughly) by all the binary
variables of all nodes of the given nice tree decomposition. Then we show that its extension complexity is
small and that a properly chosen face of it is an extension of Pϕ (G).
First, for each node b of T , depending on its type, we define a polytope Pb as follows:
|C|

z }| {
• b is a leaf. Pb consists of a single point Pb = {100 . . . 0}.
• b is an introduce or forget node. For each feasible pair of types (αi , αj ) ∈ Fp (b) of the node b, we
create a vector (db , tb ) ∈ {0, 1}2|C| with db [i] = tb [j] = 1 and all other coordinates zero. Pb is defined
as the convex hull of all such vectors.
• b is a join node. For each feasible triple of types (αh , αi , αj ) ∈ Ft (b) of the node b, we create a
vector (lb , rb , tb ) ∈ {0, 1}3|C| with lb [h] = rb [i] = tb [j] = 1 and all other coordinates zero. Pb is
defined as the convex hull of all such vectors.
It is clear that for every node b in T , the polytope Pb contains at most |C|3 vertices, and, thus, by
Proposition 1 it has extension complexity at most xc(Pb ) 6 |C|3 . Recalling our discussion in Section 3
about the size of C, we conclude that there exists a function f such that for every b ∈ V (T ), it holds that
xc(Pb ) 6 f (|ϕ|, τ ).
We create an extended formulation for Pϕ (G) by gluing these polytopes together, starting in the leaves
of T and processing T in a bottom up fashion. We create polytopes Qb for each node b in T recursively
as follows:
11

• If b is a leaf then Qb = Pb .
• If b is an introduce or forget node, then Qb = Qa ×|C| Pb where a is the child of b and the gluing is
done along the coordinates ta in Qa and db in Pb .
• If b is a join node, then we first define Rb = Qa ×|C| Pb where a is the left child of b and the gluing
is done along the coordinates ta in Qa and lb in Pb . Then Qb is obtained by gluing Rb with Qc
along the coordinates tc in Qc and rb in Rb where c is the right child of b.
The following lemma states the key property of the polytopes Qb .
Lemma 10. For every vertex y of the polytope Qb there exist X1 , . . . , Xm ⊆ V (Gb ) such that (Gb , (X1 , . . . , Xm ), η(B(b)))
is of type α where α is the unique type such that the coordinate of y corresponding to the binary variable
tb [α] is equal to one.
Proof. The proof is by induction, starting in the leaves of T and going up towards the root. For leaves,
the lemma easily follows from the definition of the polytopes Pb .
For the inductive step, we consider an inner node b of T and we distinguish two cases:
• If b is a join node, then the claim for b follows from the inductive assumptions for the children of b,
definition of a feasible triple, definition of the polytope Pb , Lemma 1 and the construction of the
polytope Qb .
• If b is an introduce node or a forget node, respectively, then, analogously, the claim for b follows from
the inductive assumption for the child of b, definition of a feasible pair, definition of the polytope
Pb , Lemma 2 or Lemma 3, respectively, and the construction of the polytope Qb .

Let c be the root node of the tree decomposition T . Consider the polytopePQc . From the construction of
Qc , our previous discussion and the Gluing lemma, it follows that xc(Qc ) 6 b∈V (T ) xc(Pb ) 6 f (|ϕ|, τ ) · n.
It remains to show that a properly chosen face of Qc is an extension of Pϕ (G). We start by observing
P|C|
P|C|
that i=1 tc [i] ≤ 1 and i=1 ρϕ (i)·tc [i] ≤ 1, where ρϕ is the indicator function defined in Subsection 3.3,
are valid inequalities for Qc .
P|C|
Let Qϕ be the face of Qc corresponding to the valid inequality
i=1 ρϕ (i)·tc [i] ≤ 1. Then, by
Lemma 10, the polytope Qϕ represents those [m]-colorings of G for which ϕ holds. The corresponding
feasible assignments of ϕ on G are obtained as follows: for every vertex v ∈ V (G) and every i ∈ {1, . . . , m}
P|C|
we set yvi = j=1 µ(αj , v, i)·ttop(v) [j]. The sum is 1 if and only if there exists a type j such that ttop(v) [j] = 1
and at the same time µ(αj , v, i) = 1; by the definition of the indicator function µ in Subsection 3.4, this
implies that v ∈ Xi . Thus, by applying the above projection to Qϕ we obtain Pϕ (G), as desired.
It is worth mentioning at this point that the polytope Qc depends only on the treewidth τ , the
quantifier rank k of ϕ and the number of free variables of ϕ. The dependence on the formula ϕ itself only
manifests in the choice of the face Qϕ of Qc and its projection to Pϕ (G).
Corollary 2. The extension complexity of the convex hull of all satisfying assignments of a given MSO2
formula ϕ on a given graph G of bounded treewidth is linear in the size of the graph G.
6. Efficient Construction of the MSO Polytope
In the previous section we have proven that Pϕ (G) has a compact extended formulation but our
definition of feasible tuples and the indicator functions µ and ρϕ did not explicitly provide a way how to
actually obtain it efficiently. That is what we do in this section.
As in the previous section we assume that we are given a graph G of treewidth τ and an MSO formula
ϕ with m free variables and quantifier rank k. We start by constructing a nice tree decomposition (T, B)
of G of treewidth τ in time f (τ ) · n [5, 26].
SO
Let C denote the set of equivalence classes of ≡M
. Because C is finite and its size is independent
k
of the size of G (Theorem 1), for each class α ∈ C, there exists an [m]-colored τ -boundaried graph
~ α , p~α ) of type α whose size is upper-bounded by a function of k, m and τ . For each α ∈ C, we fix
(Gα , X
one such graph, denote it by W (α) and call it the witness of α. Let W = {W (α) | α ∈ C}. The witnesses
12

make it possible to easily compute the indicator function ρϕ : for every α ∈ C, we set ρϕ (α) = 1 if and
only if W (α) |= ϕ, and we set ρϕ (α) = 0 otherwise.
The following Lemma is implicit in [19] in the proof of Theorem 4.6 and Corollary 4.7.
Lemma 11 ([19]). The set W and the indicator function ρϕ can be computed in time f (k, m, τ ), for
some computable function f .
It will be important to have an efficient algorithmic test for MSO[k, τ ]-elementary equivalence. This
can be done using the Ehrenfeucht-Fraı̈ssé games:
[m],τ

[m],τ

Lemma 12 ([35, Theorem 7.7]). Given two [m]-colored τ -boundaried graphs G1
and G2
, it can be
[m],τ
[m],τ
SO
decided in time f (m, k, τ, |G1 |, |G2 |) whether G1
≡M
G
,
for
some
computable
function
f.
2
k
Corollary 3. Recognizing the type of an [m]-colored τ -boundaried graph G[m],τ can be done in time
f (m, k, τ, |G|), for some computable function f .
Now we describe a linear time construction of the sets of feasible types, pairs and triples of types
F(b), Fp (b) and Ft (b) for all relevant nodes b in T . In the initialization phase we construct the set W,
using the algorithm from Lemma 11. The rest of the construction is inductive, starting in the leaves of T
and advancing in a bottom up fashion towards the root of T . The idea is to always replace a possibly
[m],τ
large graph Ga
of type α by the small witness W (α) when computing the set of feasible types for the
father of a node a.
Leaf node. For every leaf node a ∈ V (T ) we set F(a) = {α1 }. Obviously, this corresponds to the
definition in Section 3.
Introduce node. Assume that b ∈ V (T ) is an introduce node with a child a ∈ V (T ) for which F(a)
has already been computed, and v ∈ V (G) is the new vertex. For every α ∈ F(a), we first produce a
0
τ 0 -boundaried graph H τ = (H α , ~q) from W (α) = (Gα , X~α , p~α ) as follows: let τ 0 = |p~α | + 1 and H α be
obtained from Gα by attaching to it a new vertex in the same way as v is attached to Ga . The boundary
~q is obtained from the boundary p~α by inserting in it the new vertex at the same position that v has
~ α,I
in the boundary of (Ga , η(B(a))). For every subset I ⊆ {1, . . . , m} we construct an [m]-coloring Y
α,I
α,I
α
α
from X~α by setting Yi = Xi ∪ {v}, for every i ∈ I, and Yi = Xi , for every i 6∈ I. Each of these
~ α,I is used to produce an [m]-colored τ 0 -boundaried graph (H α , Y
~ α,I , ~q) and the types of
[m]-colorings Y
0
all these [m]-colored τ -boundaried graphs are added to the set F(b) of feasible types of b, and, similarly,
~ α,I , ~q),
the pairs (α, β) where β is a feasible type of some of the [m]-colored τ 0 -boundaried graph (H α , Y
are added to the set Fp (b) of all feasible pairs of types of b. The correctness of the construction of the
sets F(b) and Fp (b) for the node b of T follows from Lemma 2.
Forget node. Assume that b ∈ V (T ) is a forget node with a child a ∈ V (T ) for which F(a) has
already been computed and that the d-th vertex of the boundary η(B(a)) is the vertex being forgotten.
We proceed in a similar way as in the case of the introduce node. For every α ∈ F(a) we produce an
~ α , ~q) from W (α) = (Gα , X
~ α , p~α ) as follows: let τ 0 = |p~α | − 1,
[m]-colored τ 0 -boundaried graph (H α , Y
α
α
α ~α
~ and ~q = (p1 , . . . , pd−1 , pd+1 , . . . , pτ 0 +1 ). For every α ∈ F(a), the type β of the
H =G , Y =X
constructed graph is added to F(b), and, similarly, the pairs (α, β) are added to Fp (b). The correctness
of the construction of the sets F(b) and Fp (b) for the node b of T follows from Lemma 3.
Join node. Assume that c ∈ V (T ) is a join node with children a, b ∈ V (T ) for which F(a) and F(b)
have already been computed. For every pair of compatible types α ∈ F(a) and β ∈ F(b), we add the
type γ of W (α) ⊕ W (β) to F(c), and the triple (α, β, γ) to Ft (c). The correctness of the construction of
the sets F(c) and Ft (c) for the node b of T follows from Lemma 1.
It remains to construct the indicator functions ν and µ. We do it during the construction of the sets
of feasible types as follows. We initialize ν to zero. Then, every time we process a node b in T and we find
a new feasible type β of b, for every v ∈ B(b) and for every i for which the d-th vertex in the boundary of
~ p~) belongs to Xi , we set µ(β, b, v, i) = 1 where d is the order of v in the boundary of
W (β) = (Gβ , X,
(Gb , η(B(b)). The correctness follows from the definition of ν and the definition of feasible types. The
function µ is then straightforwardly defined using ν.
Concerning the time complexity of the inductive construction, we observe, exploiting Corollary 3, that
for every node b in T , the number of steps, the sizes of graphs that we worked with when dealing with
the node b, and the time needed for each of the steps, depend on k, m and τ only. We summarize the
main result of this section in the following theorem.
13

Theorem 3. Under the assumptions of Theorem 2, the polytope Pϕ (G) can be constructed in time
f 0 (|ϕ|, τ ) · n, for some computable function f 0 .
7. Extensions
Using our results about the glued product in Section 4 we can extend Theorem 3 to guarantee a
couple of additional non-trivial properties of a certain extended formulation of Pϕ (G). Recall that
SO
C = {α1 , . . . , αw } is the set of equivalence classes of the relation ≡M
, and that for a given formula ϕ,
k
a graph G and a tree decomposition (T, B) of G, for every node a of T , we denote the set of feasible
types of the node a by F(a), for every introduce and every forget node a of T the set of feasible pairs
of the node a by Fp (a) and for every join node a of T the set of feasible triples of the node a by Ft (a).
Moreover, let VIF denote S
the set of introduce andSforget nodes in T , VJ S
the set of join nodes and VL the
set of leaves, and let F = b∈VIF {{b} × Fp (b)} ∪ b∈VJ {{b} × Ft (b)} ∪ b∈VL {{b} × F(b)}, that is, F is
a set containing for every node b ∈ V (T ) a pair {b, F 0 (b)} where F 0 (b) is the set of feasible pairs Fp (b)
for introduce and forget nodes, the set of feasible triples Ft (b) for join nodes and the set of feasible types
F(b) for leaves.
As in the case of Theorem 2, for the sake of simplicity we again formulate and prove the main theorem
of this section in terms of graphs represented as σ2 -structures; the extension to arbitrary σ2 -structures is
straightforward.
Theorem 4. Let G = (V, ∅, {E, LV , LE }) be a σ2 -structure of treewidth τ representing a graph, let
n = |V | and let (T, B) be a nice tree decomposition of G of treewidth τ and let ϕ be an M SO1 σ2 formula
with m free variables.
Then there exist matrices A, D, C, a vector e, a function ν : C × V (T ) × V × {1, . . . , m} → {0, 1} and
a tree decomposition (T ∗ , B ∗ ) of the Gaifman graph G(A D C) such that the following claims hold:
1. The polytope P = {(y, t, f ) ∈ RV ×[m] × RC×V (T ) × RF | Ay + Dt + Cf = e,
0/1-polytope and Pϕ (G) = {y | ∃t, f : (y, t, f ) ∈ P }.

t, f ≥ 0} is a

2. P is constructively decomposable.
3. For any (y, t, f ) ∈ vert(P ), for any j ∈ C, b ∈ V (T ), v ∈ B(b) and i ∈ {1, . . . , m}, equalities
tb [j] = 1 and ν(j, b, v, i) = 1 imply that yvi = 1.
4. (a) The treewidth of (T ∗ , B ∗ ) is O(|C|3 ),
(b) T ∗ = T ,

S
(c) for every node b ∈ V (T ∗ ), j∈C {tb [j]} ⊆ B ∗ (b), and,
S
(d) j∈C {tb [j]} ∩ B ∗ (a) = ∅ for every a 6∈ δT ∗ (b).
5. A, D, C, d, ν can be computed in time O(|C|3 · n).
Let us first comment on the meaning and usefulness of the various points of the theorem. Point (1)
simply states that P is an extended formulation of Pϕ (G). However, there are variables t which allow some
interpretation of integer points of P as we will discuss further (point (3)), and there are also variables f ,
which are used to ensure constructive decomposability (point (2)).
There are currently two applications of this theorem, one due to Gajarský et al. [18] and the other by
Knop et al. [28]. What they have in common is viewing the system of linear inequalities Ay + Dt + Cf = e
with t, f ≥ 0, which defines P , as an integer linear program, because they are only interested in its
integer solutions, and then further viewing it as a constraint satisfaction problem (CSP). This allows
adding nonlinear constraints and optimizing nonconvex objective function. Then, by point (4a), this
CSP instance also has bounded treewidth, and thus can be efficiently solved by an old algorithm of
Freuder [17].
Point (3) is closely related to Lemma 10 which we needed for the proof of Theorem 2. Intuitively,
it says that we can view the variables t of integer points of P as an assignment from V (T ) to C (i.e.,
each node is assigned a type) and that knowing a type of a node b is sufficient for knowing, for each
vertex v ∈ B(b), to which free variables Xi vertex v belongs. This was used by Knop et al. [28] who study
various extensions of the MSO logic. In their work, they extend a CSP instance corresponding to the
14

system defining P with further constraints modeling the various extensions of MSO. They crucially rely
on point (4c) which allows them to add new constraints in a way which does not increase the treewidth
of the resulting CSP instance by much.
Point (2) essentially says that integer points of rP correspond to r-sets (i.e., sets of size r) of vertices
of P . This was used by Gajarský et al. [18] who study the so-called shifted combinatorial optimization
problem (SCO), where one wants to optimize a certain non-linear objective over r-sets of a given set S.
Gajarský et al. connect separable optimization over the r-dilate of a decomposable 0/1 polyhedron Q
with SCO. Thus, when S = Sϕ (G) is the set of satisfying assignments of a formula ϕ on a graph G, one
can optimize over integer points of rP in order to optimize over r-sets of Sϕ (G).
of Theorem 4. Let us give an outline of the proof first. The construction of the polytope P , and of
the corresponding system of linear inequalities describing it, is done in three phases. In each phase we
construct and examine three related objects: a certain polytope, a system of linear inequalities defining
it, and a tree decomposition of the Gaifman graph of the system of linear inequalities. We closely follow
along the lines of the proof of Theorem 2 but we modify and extend it in a way that will make it possible
to prove the additional properties. In the first phase, we construct a polytope Q0c , an analogue of the
polytope Qc from the aforementioned proof. The vertices of this polytope correspond to assignments of
feasible types to the nodes of the tree decomposition T . In the second phase, we define a polytope Q0ϕ as
a properly chosen face of the polytope Q0c , analogously to the choice of the face Qϕ of the polytope Qc .
The third phase consists only of introducing the variables yvi as a suitable linear combination of z – this
way we obtain the polytope P from the polytope Q0ϕ .
Phase 1: Constructing Q0c . In the proof of Theorem 2, we obtain the polytope Qc by gluing together
polytopes Pb , b ∈ V (T ), in a bottom-up fashion over nodes of a nice tree decomposition of G. Recall that
every Pb is a 0/1-polytope, has dimension at most 3|C| and its number of vertices is at most |C|3 . Thus,
by Corollary 1, there exists a constructively decomposable extension Pb0 of Pb describable by inequalities
of treewidth at most |C|3 + 3|C| = O(|C|3 ).
We proceed in the same way as in the construction in the proof of Theorem 2 but instead of Pb , we
glue together the polytopes Pb0 . At the same time, by Lemma 8 we combine, again in the bottom-up
fashion over nodes of the nice tree decomposition (T, B) of G, the systems of inequalities that describe
the polytopes Pb0 and also the tree decompositions of the corresponding Gaifman graphs. Let c denote the
root of the decomposition tree T as in the proof of Theorem 2, let D0 t + C 0 f = e0 with t, f ≥ 0 denote
the resulting system of inequalities describing the polytope Q0c and let (T 0 , B 0 ) denote the resulting tree
decomposition of the Gaifman graph G(D0 C 0 ).
We shall now prove that the conditions (4) hold for (T 0 , B 0 ) by induction. Then, it will be sufficient
in the later stages of the proof to show that they will not be violated.
Lemma 13. For each b ∈ V (T ), there are matrices Cb0 and Db0 such that C 0 tb + Db0 (t̄, f¯) = e0b with
tb , t̄, f¯ ≥ 0 describes the intermediate polytope Q0b obtained in the bottom-up construction, G(Cb0 Db0 ) has
3
a tree decomposition (Tb , Bb ) of treewidth O(|C|
S ), Tb is as defined before
S (i.e., a subtree of T rooted in b),
and for every node a ∈ V (Tb ), it holds that i∈C {ta [i]} ⊆ Bb (a), and i∈C {ta [i]} ∩ Bb (a0 ) = ∅ for every
a0 6∈ δTa (a).
Clearly, if these conditions hold for the root c, the conditions (4) are satisfied.
Proof. First, let b be a leaf. By Lemma 9, there is a system Cb0 tb + Db0 fb = eb with fb ≥ 0 describing
Pb0 (which contains just one point), and there is a trivial tree decomposition of G(Cb0 Db0 ) with one bag
containing all vertices. This establishes the base case of the induction.
Consider an introduce or forget node b of T with a child a, and we glue the polytopes Q0a and Pb0 . By
Lemma 9, Pb0 is described by Ab db + Cb tb + Db fb = eb with fb ≥ 0, and G(Ab Cb Db ) has a trivial tree
decomposition with one bag containing all its vertices. By the induction hypothesis, Q0a is described by
Ca0 ta + Da0 (t̄, f¯) = ea with ta , t̄, f¯ ≥ 0, where t̄ and f¯ are the t and f variables associated with the nodes
A
of Ta . Thus, the following system, where the columns C 0b correspond to the matrix Cb0 and the remaining
a
columns to the matrix Db0 , describes Q0b :
Ab db + Cb tb + Db fb
Ca0 ta

+
15

Da0 (t̄, f¯)

≥ eb

≥ ea

S Moreover, because there is a tree decomposition (Ta , Ba ) of the Gaifman graph G(Aa Ea ) such that
i∈C {ta [i]} ⊆ Ba (a), we are in the situation of the second part of Lemma 8 with A = (Ab Db ), B = Cb ,
C = Ca0 , D = Da0 . This implies that (Tb , Bb ) with Bb defined by Bb (a0 ) = Ba (a0 ) for all a0 ∈ Ta , and
Bb (b) = V (G(Ab Cb Db )), is a tree decomposition of G(C 0 D0 ) which has the desired properties.
The situation is analogous for the join node. By the first part of Lemma 8 together with the induction
hypothesis, the treewidth of (Tb , Bb ) is clearly at most O(|C|3 ).
Phase
2: Taking the face Q0ϕ . We take the face Q0ϕ of Q0c corresponding
to the valid inequality
P
P
t
ρ
ρ
(t)·z
≤
1.
That
corresponds
to
adding
the
equality
(t)·t
[j] = 1 to the system
ϕ
ϕ
c
c
t∈C
j∈C
D0 t + C 0 f = e0 . Let us denote D00 t + C 00 f = e00 the system obtained from D0 t + C 0 f = e0 by adding
the aforementioned equality. Adding the new equality corresponds to adding edges to G(D0 C 0 ) which
are connecting vertices tc [j]. Since all variables tc [j] belong to the bag B 0 (c), the tree decomposition
conditions are not violated by adding these edges and (T 0 , B 0 ) is a tree decomposition of G(D00 C 00 ) as
well. Thus, the treewidth of G(D00 C 00 ) is the same as the treewidth of G(D0 C 0 ).
We will now show that since Q0c is decomposable and a 0/1-polytope, Q0ϕ is decomposable as well.
Let r ∈ N and consider any x ∈ rQ0ϕ . Because x ∈ rQ0ϕ ⊆ rQ0c , there exist x1 , . . . , xr ∈ Q0c such that
P i
P
x. Because x ∈ rQ0ϕ , it satisfies t∈C ρϕ (t)·zct = r, and because Q0ϕ is a 0/1-polytope, every xi
i x =P
satisfies j∈C ρϕ (t)·tc [j] = 1. This implies that xi ∈ Q0ϕ for all i = 1, . . . , r.
Phase 3: Obtaining P by adding variables y. To obtain P from Q0ϕ , it remains to add projections
P
µ(t, v, i)·ttop(v) [j] for each v ∈ V and i ∈ {1, . . . , m}. Now consider the system Ay + Dt + Cf = e
yvi =
j∈C

which is thus obtained.
Regarding the treewidth of G(A D C), note that the sum defining each yvi only involves variables
associated with the node top(v). Specifically, Ay + Dt + Cf = e can be written as
0y + D00 t + C 00 f = e00
−Iy + Λ t + 0 f = 0
where the block (−I Λ 0) corresponds to the projections to yvi .
Fix v ∈ V . Then in G(A D C) the variable yvi corresponds to a vertex connected to vertices ttop(v) [j]
for which µ(j, v, i) = 1, all of which belong to one bag B = B 0 (top(v)). A decomposition (T ∗ , B ∗ ) of
G(A D C) can be obtained from (T 0 , B 0 ) by adding, for every i ∈ {1, . . . , m}, the vertex corresponding
to yvi to the bag B. This increases the width of B by at most m. Since top(v) is distinct for every v ∈ V ,
this operation can be performed independently for every v, resulting in a decomposition of width at most
O(|C|3 ) + m = O(|C|3 ), satisfying the claimed properties (4).
Regarding constructive decomposability, we use Lemma 6. The polytope Q0ϕ is constructively
decomposable, and there is a linear projection π with integer coefficients such that Pϕ (G) = π(Q0ϕ ). Thus
P = {(π(t), t, f ) | (t, f ) ∈ Q0ϕ } is constructively decomposable, satisfying property (2).
Finally, Theorem 3 shows that A, D, C, e and ν can be constructed in the claimed time, satisfying
property (5), and by the definition of ν and Lemma 10, condition (3) is also satisfied, completing the
proof.
As a corollary, we have the following.
Corollary 4. Under the assumptions of Theorem 2, xcdec (Pϕ (G)) ≤ f (|ϕ|, τ ) · n.
7.1. Cliquewidth
The results of this paper can be extended also to graphs of bounded clique-width, a more general class
of graphs, at the cost of restricting our logic from MSO2 to MSO1 (or, equivalently, restricting it from
MSO1 over σ2 to MSO1 over σ1 ). A γ-expression is a concept analogous to a tree decomposition.
Theorem 5. Let G be a graph of clique-width cw(G) = γ represented as a σ1 -structure, let ψ be an
MSO1 formula with m free variables, and let
Pψ (G) = conv ({y ∈ {0, 1}nm | y satisfies ψ}) .
Then xc(Pψ (G)) ≤ f (|ψ|, γ) · n for some computable function f .
Moreover, if G is given along with its γ-expression Γ, Pψ (G) can be constructed in time f (|ψ|, γ) · n.
16

While we could prove Theorem 5 directly using notions analogous to feasible types and tuples, it is
easier to use a close relationship between cliquewidth and treewidth:
Lemma 14 ([18, Lemma 4.14]). Let G be a graph of clique-width cw(G) = γ given along with its
γ-expression Γ, and let ψ be an MSO1 formula. One can, in time O(|V (G)| + |Γ| + |ψ|), compute a tree
T and an MSO1 formula ϕ such that V (G) ⊆ V (T ) and
for every X, T |= ϕ(X), if and only if X ⊆ V (G) and G |= ψ(X).
of Theorem 5. Let Γ be some γ-expression of G. Consider the tree T of Lemma 14 derived from G and
γ and the MSO1 formula ϕ derived from ψ. By the relationship between G and T and ψ and ϕ of
Lemma 14, the polytope Pϕ (T ) is an extended formulation of Pψ (G). Thus, by applying Theorem 2 to T
and ϕ suffices to show that xc(Pψ (G)) ≤ xc(Pϕ (T )) ≤ f (|ψ|, γ) · n for some computable function f . If a
γ-expression of G is provided, clearly the proof becomes constructive.
For simplicity, we have required that G comes along with its γ-expression to obtain a constructivity
in Theorem 5. This is because it is currently not known how to efficiently construct a γ-expression for an
input graph of fixed clique-width γ. However, one may instead use the result of [21] which constructs in
FPT time a so-called rank-decomposition of G which can be used as an approximation of a γ-expression
for G with up to an exponential jump, but this does not matter for a fixed parameter γ in theory.
7.2. Courcelle’s Theorem and Optimization.
It is worth noting that even though linear time optimization versions of Courcelle’s theorem are
known, our result provides a linear size LP for these problems out of the box. Together with a polynomial
algorithm for solving linear programming we immediately get the following:
Theorem 6. Given a graph G on n vertices with treewidth τ , a formula ϕ ∈ MSO with m free variables
and real weights wvi , for every v ∈ V (G) and i ∈ {1, . . . , m}, the problem


m
 X X

opt
wvi · yvi y satisfies ϕ


v∈V (G) i=1

where opt is min or max, is solvable in time polynomial in the input size.
8. Acknowledgements
We thank the anonymous reviewers for pointing out existing work and shorter proof of the Glueing
lemma, among various other improvements.
References
[1] S. Arnborg, J. Lagergren, and D. Seese. Easy problems for tree-decomposable graphs. Journal of
Algorithms, 12(2):308–340, June 1991.
[2] D. Avis and H. R. Tiwary. On the extension complexity of combinatorial polytopes. In Proc.
ICALP(1), pages 57–68, 2013.
[3] S. Baum and L. E. Trotter Jr. Integer rounding and polyhedral decomposition for totally unimodular
systems. In Optimization and Operations Research, pages 15–23. Springer, 1978.
[4] D. Bienstock and G. Munoz. LP approximations to mixed-integer polynomial optimization problems.
ArXiv e-prints, Jan. 2015.
[5] H. L. Bodlaender. A linear time algorithm for finding tree-decompositions of small treewidth. In
Proc. STOC, pages 226–234, 1993.
[6] H. L. Bodlaender. Treewidth: characterizations, applications, and computations. In Proc. of WG,
volume 4271 of LNCS, pages 1–14. Springer, 2006.
17

[7] G. Braun, S. Fiorini, S. Pokutta, and D. Steurer. Approximation limits of linear programs (beyond
hierarchies). Math. Oper. Res., 40(3):756–772, 2015.
[8] G. Braun, R. Jain, T. Lee, and S. Pokutta. Information-theoretic approximations of the nonnegative
rank. Computational Complexity, 26(1):147–197, 2017.
[9] A. Buchanan and S. Butenko. Tight extended formulations for independent set, 2014. Available on
Optimization Online.
[10] M. Conforti, G. Cornuéjols, and G. Zambelli. Extended formulations in combinatorial optimization.
Annals of Operations Research, 204(1):97–143, 2013.
[11] M. Conforti and K. Pashkovich. The projected faces property and polyhedral relations. Mathematical
Programming, pages 1–12, 2015.
[12] B. Courcelle. The monadic second-order logic of graphs I: Recognizable sets of finite graphs.
Information and Computation, 85:12–75, 1990.
[13] B. Courcelle, J. A. Makowsky, and U. Rotics. Linear time solvable optimization problems on graphs
of bounded clique width. In Proc. of WG, volume 1517 of LNCS, pages 125–150, 1998.
[14] B. Courcelle and M. Mosbah. Monadic second-order evaluations on tree-decomposable graphs.
Theoretical Computer Science, 109(1–2):49–82, 1 Mar. 1993.
[15] Y. Faenza, S. Fiorini, R. Grappe, and H. R. Tiwary. Extended formulations, nonnegative factorizations,
and randomized com. protocols. Math. Program., 153(1):75–94, 2015.
[16] S. Fiorini, S. Massar, S. Pokutta, H. R. Tiwary, and R. de Wolf. Exponential lower bounds for
polytopes in combinatorial optimization. J. ACM, 62(2):17, 2015.
[17] E. C. Freuder. Complexity of K-tree structured constraint satisfaction problems. In Proc. of the 8th
National Conference on Artificial Intelligence, pages 4–9, 1990.
[18] J. Gajarský, P. Hliněný, M. Koutecký, and S. Onn. Parameterized Shifted Combinatorial Optimization.
ArXiv e-prints, Feb. 2017.
[19] G. Gottlob, R. Pichler, and F. Wei. Monadic datalog over finite structures with bounded treewidth.
In Proc. PODS, pages 165–174, 2007.
[20] B. Grünbaum. Convex Polytopes. Wiley Interscience Publ., London, 1967.
[21] P. Hliněný and S. Oum. Finding branch-decompositions and rank-decompositions. SIAM J. Comput.,
38(3):1012–1032, 2008.
[22] V. Kaibel. Extended formulations in combinatorial optimization. Optima, 85:2–7, 2011.
[23] V. Kaibel and A. Loos. Branched polyhedral systems. In Proc. IPCO, volume 6080 of LNCS, pages
177–190. Springer, 2010.
[24] V. Kaibel and K. Pashkovich. Constructing extended formulations from reflection relations. In Proc.
IPCO, volume 6655 of LNCS, pages 287–300. Springer, 2011.
[25] L. Kaiser, M. Lang, S. Leßenich, and C. Löding. A Unified Approach to Boundedness Properties in
MSO. In Proc. of CSL, volume 41 of LIPIcs, pages 441–456, 2015.
[26] T. Kloks. Treewidth: Computations and Approximations, volume 842 of LNCS. Springer, 1994.
[27] J. Kneis, A. Langer, and P. Rossmanith. Courcelle’s theorem - A game-theoretic approach. Discrete
Optimization, 8(4):568–594, 2011.
[28] D. Knop, M. Koutecký, T. Masařı́k, and T. Toufar. Simplified algorithmic metatheorems beyond
MSO: Treewidth and neighborhood diversity, Mar. 1 2017. Accepted to WG 2017.

18

[29] P. G. Kolaitis and M. Y. Vardi. Conjunctive-query containment and constraint satisfaction. In Proc.
PODS, 1998.
[30] P. Kolman and M. Koutecký. Extended formulation for CSP that is compact for instances of bounded
treewidth. Electr. J. Comb, 22(4):P4.30, 2015.
[31] S. Kreutzer. Algorithmic meta-theorems. In Proc. of IWPEC, volume 5018 of LNCS, pages 10–12.
Springer, 2008.
[32] A. Langer, F. Reidl, P. Rossmanith, and S. Sikdar. Practical algorithms for MSO model-checking on
tree-decomposable graphs. Computer Science Review, 13-14:39–74, 2014.
[33] M. Laurent. Sums of squares, moment matrices and optimization over polynomials. In Emerging
applications of algebraic geometry, pages 157–270. Springer, 2009.
[34] J. R. Lee, P. Raghavendra, and D. Steurer. Lower bounds on the size of semidefinite programming
relaxations. In Proc. STOC, pages 567–576, 2015.
[35] L. Libkin. Elements of Finite Model Theory. Springer-Verlag, Berlin, 2004.
[36] F. Margot. Composition de polytopes combinatoires: une approche par projection. PhD thesis, École
polytechnique fédérale de Lausanne, 1994.
[37] R. K. Martin, R. L. Rardin, and B. A. Campbell. Polyhedral characterization of discrete dynamic
programming. Oper. Res., 38(1):127–138, Feb. 1990.
[38] A. Schrijver. Theory of Linear and Integer Programming. Wiley-Interscience Series in Discrete
Mathematics. John Wiley & Sons, 1986.
[39] M. Sellmann. The polytope of tree-structured binary constraint satisfaction problems. In Proc.
CPAIOR, volume 5015 of LNCS, pages 367–371. Springer, 2008.
[40] M. Sellmann, L. Mercier, and D. H. Leventhal. The linear programming polytope of binary constraint
problems with bounded tree-width. In Proc. CPAIOR, volume 4510 of LNCS, pages 275–287. Springer,
2007.
[41] F. Vanderbeck and L. A. Wolsey. Reformulation and decomposition of integer programs. In 50 Years
of Integer Programming 1958-2008, pages 431–502. Springer, 2010.
[42] L. A. Wolsey. Using extended formulations in practice. Optima, 85:7–9, 2011.
[43] M. Yannakakis. Expressing combinatorial optimization problems by linear programs. J. Comput.
Syst. Sci., 43(3):441–466, 1991.
[44] G. M. Ziegler. Lectures on Polytopes, volume 152 of Graduate Texts in Mathematics. Springer-Verlag,
1995.

19

