Optimal Extended Formulations from Optimal Dynamic Programming Algorithms

1 Introduction

Computational problems arising in a wide variety of subfields of artificial intelligence can be formalized as vertexsubset problems, such as INDEPENDENT SET, DOMINATING SET, VERTEX COVER, etc. Two prominent algorithmic approaches to attack these problems are dynamic programming over tree-like structures, and linear programming. While the former approach is suitable to solve vertex subset problems on graphs of small width, such as treewidth [Marx, 2007] and cliquewidth [Courcelle et al., 2000], the latter approach yields practical algorithms whenever the space of feasible solutions can be defined using a system of linear inequalities of moderate size [Hu and Laurent, 2019; Aprile et al., 2017].

Vertex subset problems that are NP-hard do not admit efficient linear programming formulations assuming P ̸= NP, and in some cases it can be even shown unconditionally that formulations for certain problems require exponential size [Yannakakis, 1988; Fiorini et al., 2015; De Simone, 1990; G¨o¨os et al., 2018a]. Nevertheless, recently there has been growing interest in the study of linear formulations of combinatorial polytopes parameterized by structural parameters of the input graph, such as treewidth and cliquewidth [Seif, 2019; Aboulker et al., 2019; Buchanan and Butenko, 2015; Kolman et al., 2020]. In this work, we contribute with this line of research by establishing a sharp connection between dynamic programming algorithms operating on tree decompositions and linear programming theory.

On the one hand, our results allow us to show that efficient solution-preserving dynamic programming algorithms parameterized by treewidth can be used to define small linear programming formulations. On the other hand, unconditional lower bounds obtained in the realm of the theory of extended formulations can be used to provide unconditional lower bounds on the table-complexity of solution-preserving dynamic programming algorithms expressible in the dynamic programming core model (DP-core model)[Baste et al., 2022; de Oliveira Oliveira and Vadiee, 2023].

1.1 Our Results

Our main result (Theorem 14) states that if a vertex subset problem Π can be solved by a solution-preserving DP-core of table complexity α(k, n) when processing a width-k tree decomposition of an n-vertex graph G, then the solution polytope of Π on G has extension complexity O(α(k, n) · n). Intuitively, problems that can be solved by solution-preserving DP-cores with small table complexity yield solution polytopes of small extension complexity. Conversely, lower bounds on the extension complexity of solution polytopes of a given problem Π yield lower bounds on the table complexity of solution-preserving DP-algorithms solving Π.

1.2 Proof Techniques

We formalize the notion of a dynamic programming algorithm parameterized by treewidth using an extension of the DP-core model introduced in [Baste et al., 2022] and further developed in [de Oliveira Oliveira and Vadiee, 2023]. The main conceptual addition to these models is an axiomatic definition of the notion of a solution-preserving dynamic programming algorithm. Intuitively, this notion formalizes dynamic programming algorithms satisfying two properties: first, any subset of vertices obtained by backtracking is a solution for the problem in question. Second, every solution should be retrievable by backtracking. It is worth noting that in general, dynamic programming algorithms may not be solution preserving. For instance, if one is simply interested in determining whether a solution exists then some solutions may be discarded during the dynamic programming process.

The bridge between dynamic programming and linear programming is made within the context of tree automata theory. More specifically, we define the notion of a T-shaped tree automaton, where T is a tree. Intuitively, these are automata accepting sets of terms over a given alphabet Σ, all of which have the same underlying tree-structure. The state set of such an automaton A is partitioned into a collection of cells, one cell Qu per node u of T, and we define the width of A as the size of the largest cell. We then show that if A is a T-shaped tree automaton of width w(A), the polytope P(A) whose vertices correspond to terms accepted by A has extension complexity O(|T| · (w(A) + |Σ|)) (Corollary 6). Finally, we show that if D is a solution-preserving DP-core of table complexity α(k, n) solving a problem Π, then given an n-vertex graph G together with a tree decomposition T of width at most k and underlying tree structure T, one can construct a T -shaped tree automaton of width α(k, n) whose accepted terms encode solutions for Π in G (Theorem 13). By combining Theorem 13 with Corollary 6, we infer that the extension complexity of the solution polytope of Π on G is upper bounded by O(α(k, n) · n).

1.3 Generalizations

Although for simplicity of exposition our main results will be stated in terms of vertex subset problems, it is worth noting that these results also generalize to edge subset problems, where the goal is to find a subset of edges satisfying a given condition (for instance, CUTℓ, HAMILTONIANCYCLE), and to problems where feasible solutions are tuples of subsets of vertices, edges, or both. For instance for each fixed d, the d-COLORING problem is a problem where the goal is to partition the vertex set of the graph into d subsets, each of which is an independent set. Extensions for the cases mentioned above are dealt with in the full version of this paper.

2 Preliminaries

2.1 Basic Definitions

We denote by N the set of natural numbers and by N+ the set of positive natural numbers. For each n ∈ N, we let [n] = {1, . . . , n}. In particular, [0] = ∅. Given a set S, the set of subsets of S is denoted by P(S), and the set of finite subsets of S is denoted by Pfin(S). Given a function f : S → R, and S′ ⊆ S, we let f(S′ ) = {f(s) | s ∈ S′ } be the image of S′ under f.

We define a graph as a triple G = (V, E, ρ), where V ⊂ N is a finite set of vertices, E ⊂ N is a finite set of edges and ρ ⊂ E×V is an incidence relation. For an edge e ∈ E, we let endpts(e) = {v ∈ V |(e, v) ∈ ρ} denote the set of vertices incident to e. We may write VG, EG and ρG to denote sets V , E and ρ. We define the empty graph as the graph (∅, ∅, ∅) with neither vertices, nor edges. We let GRAPHS denote the set of all graphs.

An isomorphism from a graph G to a graph H is a pair of functions ϕ = (ϕ1, ϕ2) where ϕ1 : VG → VH is a bijection from the vertex set of G to the vertex set of H and ϕ2 : EG → EH is a bijection from the edge set of G to the edge set of H such that for each vertex v ∈ VG and each edge e ∈ EG, we have that (e, v) ∈ ρG if and only if (ϕ2(e), ϕ1(v)) ∈ ρH. If there exists such a bijection, we say that graphs G and H are isomorphic and denote this by G ∼ H.

2.2 Vertex Subset Problems

Definition 1 (Vertex Subset Problem). A vertex subset problem is a subset Π ⊂ GRAPHS ×Pfin(N) where the following conditions are satisfied for each pair (G, X) ∈ Π:

1. for each graph H isomorphic to G, and each isomorphism ϕ = (ϕ1, ϕ2) from G to H, (H, ϕ1(X)) ∈ Π.

Given a graph G, we say that a subset X ⊆ VG is a solution for Π in G if (G, X) ∈ Π. The set of solutions for Π in G is denoted by

For example, for each ℓ ∈ N+, INDEPENDENTSETℓ denotes the vertex subset problem consisting of all pairs (G, X) where G is a graph and X is an independent set of size at least ℓ in G, that is, a subset of vertices where no pair of vertices is connected by an edge. Other prominent examples of vertex subset problems are VERTEXCOVERℓ, DOMINATINGSETℓ and CLIQUEℓ.

2.3 Solution Polytopes

Let X = {x1, x2, . . . , xn} be a set of variables. A vector over X is a function v : X → R. We say that a vector v : X → R satisfies an inequality ∑i αixi ≤ b if the inequality holds whenever each variable xi is replaced by the value v(xi). That is to say, if ∑i αiv(xi) ≤ b. A vector v is a convex combination of a set of vectors U = {v1, . . . , vm} if v = α1v1+α2v2+· · ·+αmvm for some non-negative real numbers αi such that ∑i αi = 1. The convex hull of U is the set conv(U) of all convex combinations of vectors in U. We note that conv(U) is a polytope, and as such can be defined as the set of solutions of a system of linear inequalities.

Let G be an n-vertex graph, and let X ⊆ VG. We let ˆX : X → R denote the vector over variables X = {xv : v ∈ VG} where for each v ∈ VG, ˆX(xv) = 1 if and only if v ∈ X. Given a vertex subset problem Π and a graph G, we let PΠ(G) be the polytope defined as the convex hull of vectors associated with solutions of Π in G. More specifically, PΠ(G) = conv({ ˆX : X ∈ SolΠ(G)}).

2.4 Addressed Trees

An addressed tree is a four-tuple T = (N, F, r, γ) denoting a rooted tree with nodes N, root r ∈ N, arcs F ⊆ N ×N directed from the leaves towards the root, and arc-labeling function γ : F → N that labels the arcs of T with numbers in such a way that for each u ∈ N, the arcs in the set In(u) = {(v, u) | (v, u) ∈ F} are injectively labeled with numbers from {1, . . . , |In(u)|}. For each arc (v, u) ∈ In(u), we say that v is the i-th child of u if γ(v, u) = i. We may write N(T) to denote the set of nodes of T , and r(T) to denote the root of T .

3 Dynamic Programming Cores for Tree Decompositions

The formalism we use to express dynamic programming algorithms operates on edge-introducing tree decompositions. For a matter of consistency with the notation in the remainder of the paper, our definition of tree decompositions uses a slightly distinct notation than the one typically used in the literature.

We define an edge-introducing tree decomposition of a graph G as a triple T = (T,B, ξ) where T is an addressed tree, ξ : E(G) → N(T) is an injective function, and B : N(T) → P(VG) is a function satisfying the following conditions:

1. For each vertex v ∈ V (G), there is a node u ∈ N(T) such that v ∈ B(u);
2. for each edge e ∈ E(G), endpts(e) ⊆ B(ξ(e));
3. for each v ∈ V (G), the set {u ∈ N(T) | v ∈ B(u)} induces a connected sub-tree of T .

The width of T is defined as maxu |B(u)| - 1. The treewidth of a graph G, denoted by tw(G), is defined as the minimum width of an edge-introducing tree decomposition of G.

An edge-introducing tree decomposition T is said to be nice if each node u ∈ N(T) has at most two children and the following conditions are satisfied: If u has two children u′ and u′′ , then B(u) = B(u′ ) = B(u′′ ). In this case, u is called a join node. If u has a single child u′ , then it either introduces a vertex v (meaning that B(u)\B(u′ ) = {v}), or it forgets a vertex v (meaning that B(u′ )\B(u) = {v}), or it introduces an edge e (meaning that B(u) = B(u′ ) and ξ(e) = u). If u is a leaf node, or the root node, then B(u) = ∅. In this work, we assume that edge-introducing tree decompositions are nice. This assumption is without loss of generality, since any tree decomposition of width k of a graph G can be transformed into a nice edge-introducing tree decomposition of G of width at most k in time O(k · |N(T )|) [Kloks, 1994].

We formalize the notion of a dynamic programming algorithm operating on tree decompositions using the notion of a dynamic programming core. Our formalism is essentially equivalent in expressiveness as the notion of a DP-core introduced in [Baste et al., 2022] in the sense that dynamic programming algorithms developed in either model can be easily converted to each other with minor adaptations.

Definition 2. A DP-core is a 6-tuple D whose components are specified as follows.

1. Leaf is a finite non-empty subset of {0, 1}∗ .

1. IntroVertex : N×{0, 1}∗ →Pfin({0, 1}∗ )
2. IntroEdge : N×N×{0, 1}∗ →Pfin({0, 1}∗ ).
3. ForgetVertex : N × {0, 1}∗ → Pfin({0, 1}∗ ).
4. Join : {0, 1}∗ ×{0, 1}∗ →Pfin({0, 1}∗ ).
5. Final : {0, 1}∗ → {0, 1}.

For each S ⊆ {0, 1}∗ , we define IntroVertex(v, S) = ⋃w∈S IntroVertex(v,w). The extension of the remaining components of D to subsets of strings is defined analogously.

Intuitively, a DP-core D is a specification of a dynamic programming algorithm that operates on edge-introducing tree decompositions of graphs. The algorithm processes such a tree decomposition T = (T,B, ξ) from the leaves towards the root, assigning to each node u ∈ N(T) a finite subset of strings Γ(u) according to the following inductive process.

1. If u is a leaf node of T, Γ(u) = Leaf
2. If u is an internal node of T with a unique child u′ , then
3. (a) Γ(u) = IntroVertex(v, Γ(u′ )) if vertex v is introduced at u.
4. (b) Γ(u) = ForgetVertex(v, Γ(u′ )) if vertex v is forgotten at u.
5. (c) Γ(u) = IntroEdge(v, v′ , Γ(u′ )) if an edge connecting v and v′ is introduced at u.
6. If u is a join node of T with children u′ and u′′ then Γ(u) = Join(Γ(u′ ), Γ(u′′ )).

We say that D accepts the tree decomposition T if the set Γ(r(T)) associated with the root node of T has a final string. That is to say, w ∈ Γ(r(T )) with Final(w) = 1.

Definition 3. We say that D solves a vertex subset problem Π if for each graph G, and each tree decomposition T of G, D accepts T if and only if SolΠ(G) ̸= ∅.

We say that D has table complexity α(k, n) if for each n-vertex graph G, each tree decomposition T = (T, B, ξ) of G of width at most k, and each node u ∈ N(T ), the set Γ(u) has at most α(k, n) elements.

A DP-core for Independent Set. As an illustration, we define below a DP-core D for the problem INDEPENDENTSETℓ. It is enough to specify the action of each component of the core on strings that encode pairs of the form (S, c) where S ⊆ N and c ∈ N. The particular encoding itself is not relevant, as long as it is fixed. We let D be the DP-core whose components are defined as follows.

• Leaf = {(∅, 0)}.
• IntroVertex(v, (S, c)) = {(S, c), (S ∪ {v}, c +1)}.
• IntroEdge(v, v′ , (S, c)) = { ∅ if {v, v′ } ⊆ S {(S, c)} otherwise.
• ForgetVertex(v, (S, c)) = {(S\{v}, c)}.

• Join((S1, c1), (S2, c2)) = { ∅ if S1 ̸= S2 {(S1, c1 + c2 - |S1|)} otw.
• Final((S, c)) = 1 if and only if c ≥ ℓ.

The next proposition implies that the DP-core D specified above solves INDEPENDENTSETℓ. Below, Gu means the subgraph of G induced by the set ⋃t∈N(Tu) B(t), where Tu is the sub-tree of T rooted at u.

Proposition 4. Let G be a graph, T = (T,B, ξ) be a tree decomposition of G. Then, for each u ∈ N(T), and each pair (S, c) ∈ P(N) × N, (S, c) belongs to Γ(u) if and only if the graph Gu has an independent set I of size at least c such that S = I ∩ B(u).

In particular, G has an independent set of size at least ℓ if and only for some ℓ′ ≥ ℓ, the pair (∅, ℓ′ ) belongs to Γ(r(T)), and this happens if and only if T is accepted by D. We also note that by Proposition 4, we have that if T has width k and G has n vertices, then |Γ(u)| ≤ 2k · |VG|. Therefore, the table complexity of D is upper bounded by 2k · n. Although very simple, this the DP-core defined above is essentially optimal under SETH [Lokshtanov et al., 2018].

4 The Polytope of a T-Shaped Language

Let Σ be a set of symbols. A term over Σ is a pair τ = (T, λ) where T is an addressed tree, and λ : N(T ) → Σ is a function that labels each node of T with a symbol from Σ. We say that a term τ is T-shaped if τ = (T, λ) for some λ. Whenever clear from the context, we may write τ(u) to denote the label λ(u). We let Terms(Σ) denote the set of all terms over Σ.

4.1 T-Shaped Tree Automata

Let T be an addressed tree. A T-shaped tree automaton is a tuple A = (Σ,Q, F,∆) where Q = ⋃u Qu is a set of states, partitioned into a collection of subsets {Qu}u∈N(T), F ⊆ Qr(T) is a set of final states, and ∆ = ⋃u ∆u is a set of transitions, partitioned into a collection of subsets {∆u}u∈N(T) such that the following condition is satisfied: for each node u ∈ N(T ) with children u1, . . . , us,

Let τ = (T, λ) be a term over Σ. A trace for τ in A is a function ρ : N(T) → Q such that for each node u ∈ N(T) with children u1, . . . , us, the tuple (ρ(u1), . . . , ρ(us), τ(u), ρ(u)) is a transition in ∆u. We say that ρ is an accepting trace if ρ(r(T)) ∈ F. We say that τ is accepted by A if there is an accepting trace ρ for τ in A. The language of A is the set L(A) of all terms accepted by A.

4.2 The Polytope P(A)

Let T be an addressed tree and Σ be a set of symbols. We let

denote the set of variables associated with T and Σ. Given a T -shaped term τ ∈ Terms(Σ), we let ˆ τ : X(T,Σ) → {0, 1} be the 0/1 vector defined by setting, for each u ∈ N(T) and each symbol a ∈ Σ, ˆ τ(xu,a) = 1 if τ(u) = a and ˆ τ (xu,a) = 0 otherwise. Given a T -shaped tree automaton A, we define the polytope associated with A, denoted by P(A), as the convex hull of all vectors encoding terms accepted by A:

4.3 An Extended Formulation for P(A)

A polytope P ′ is an extended formulation of a polytope P if P is a projection of P ′ . The next theorem, which is the main result of this section, states that polytopes associated with Tshaped tree automata have extended formulations that can be defined by systems of linear inequalities whose size is linear on the number of states plus the number of transitions of the automata.

Theorem 5. Let A = (Σ,Q, F,∆) be a T-shaped tree automaton. The polytope P(A) has an extended formulation with O(|Q| + |∆|) extension variables and O(|Q| + |T | · |Σ|) inequalities.

We define the width of a T-shaped tree automaton A, denoted by w(A), as the maximum size of a state cell:

Since a T -shaped tree automaton of width w can have at most w · |T| states, Theorem 5 immediately implies the following corollary:

Corollary 6. Let A = (Σ,Q, F,∆) be a T-shaped tree automaton of width w(A). The polytope P(A) has extension complexity O(|T | · (w(A) + |Σ|)).

In the remainder of this section we define an extended formulation for the polytope P(A) satisfying the conditions of Theorem 5. We start by specifying the extension variables, which we split into two sets. The first set,

has one variable yu,q for each node u in N(T) and each state q in Qu. We call the elements of Y(A) state variables. The second set,

has one variable zu,δ for each node u in N(T) and each transition δ in ∆u. We call the elements of Z(A) transition variables. We let var(A) = X(T, Σ) ∪ Y(A) ∪ Z(A) be the set of variables associated with A. In what follows, we will refer to the sets X(T, Σ), Y(A) and Z(A) simply as X, Y and Z respectively.

Given a transition δ = (q1, . . . , qs, a, q) in ∆, we say that q is the consequent state of δ, while for each i ∈ [s], qi is an antecedent state of δ. We denote the consequent state q by cnq(δ) and the set of antecedent states {q1, . . . , qs} by ant(δ). We denote by symb(δ) the symbol a of δ.

Let zu,δ be a transition variable in Z for some u ∈ N(T) and transition δ ∈ ∆u. If q = cnq(δ), we say that zu,δ is an incoming transition variable of yu,q. If u′ is a child of u and q′ ∈ ant(δ), we say that zu,δ is an outgoing transition variable of yu′ ,q′ .

Definition 7. Let A = (Σ,Q, F,∆) be a T-shaped tree automaton, τ = (T, λ) be a term in L(A), and ρ : N(T) → Q be a trace for τ in A. We let ˆ ρ be the 0/1 vector over var(A) satisfying the following conditions:

1. For each xu,a ∈ X, ˆ ρ(xu,a) = 1 iff λ(u) = a.
2. For each yu,q ∈ Y, ˆ ρ(yu,q) = 1 iff ρ(u) = q.
3. For each zu,δ in Z, ˆ ρ(zu,δ) = 1 iff δ = (ρ(u1), . . . , ρ(us), λ(u), ρ(u)), where u1, . . . , us are the children of u.

Let τ be a term in L(A), and ρ be a trace for τ in A. Then by restricting the vector ˆ ρ to the variables in X , we obtain the vector ˆ τ associated with τ. This implies that the polytope

defined as the convex-hull of vectors corresponding to accepting traces in A is an extended formulation of the polytope P(A). Note that Y has |Q| variables, while the set Z has |∆| variables. Therefore, besides the main variables in X , we are using |Q| + |∆| extension variables to define Pex(A).

Next, we will show that Pex(A) can be defined as the set of solutions of a system of linear inequalities LA containing O(|Q|+|T |·|Σ|) linear constraints. The first set of constraints ensure that all variables in a solution should assume values between 0 and 1. More specifically, for each main variable xu,a ∈ X, each state variable yu,q ∈ Y, and each transition variable zu,δ ∈ Z,

Let r = r(T) be the root of T. The following constraints ensure that in an integral solution, there is exactly one final state q ∈ F for which variable yr,q is set to 1. Additionally, in such a solution, for each state q ∈ Qr\F the variable yr,q is set to 0.

The next set of constraints ensure that for each node u ∈ N(T), and each state q ∈ Qu, for any integral solution that sets variable yu,q to 1 there is some transition δ ∈ ∆u with consequent q such that zu,δ is set to 1.

The next set of constraints ensure that for each node u ∈ N(T) distinct from the root r, and each state q ∈ Q, for any integral solution that sets variable yu,q to 1 there is some transition z ∈ ∆par(u) having q as an antecedent such that zu,δ is set to 1. Here, par(u) denotes the parent of u.

Finally, the next set of equations ensure that if an integral solution sets a main variable xu,a ∈ X to 1, then there is some transition δ ∈ ∆u with symb(δ) = a such that the transition variable zu,δ is also set to 1.

Theorem 5 is a direct consequence of the following theorem, stating that the set of inequalities LA defines the polytope Pex(A).

Theorem 8. Let A = (Σ,Q, F,∆) be a T-shaped tree automaton. A vector µ belongs to Pex(A) if and only if µ satisfy all inequalities in LA.

The proof of Theorem 8 is carried out in detail in the full version of this work. The proof is split into three parts. In the first part, we show that for each trace ρ in A, the 0/1- vector ˆ ρ satisfies the system of linear inequalities LA. This implies that the polytope Pex(A) is contained in the polytope P(LA) defined by LA. In the second part, we show that if µ is an integral vector satisfying all inequalities of LA, then there is some trace ρ of A such that ˆ ρ = µ. This shows that at least the integral solutions of LA are contained in Pex(A). Finally, in the third part, we show that any vertex of the polytope defined by LA is a 0/1-vector. Therefore, since 0/1-vectors cannot be convex combinations of other 0/1 vectors, we have that the vertices of P(LA) are precisely the 0/1-vectors satisfying all constraints in LA. This shows that P(LA) = Pex(A), and concludes the proof of Theorem 8.

5 Witness Trees and Solution Polytopes

In this section, we let Π be a vertex subset problem, D be a DP-core solving Π, G be a graph and T be a tree decomposition of G.

Definition 9. A D-witness-tree for T is a function W : N(T ) → {0, 1}∗ satisfying the following properties:

1. Final(W(r(T))) = 1,
2. W(u) ∈ Leaf if u is a leaf node,
3. If u is a node with a single child u′ ,
4. (a) W(u) ∈ IntroVertex(v,W(u′ )) if vertex v is introduced at node u,
5. (b) W(u) ∈ ForgetVertex(v,W(u′ )) if vertex v is forgotten at node u,
6. (c) W(u) ∈ IntroEdge(v, v′ ,W(u′ )) if an edge an edge e with endpts(e) = {v, v′ } is introduced at node u.
7. If u is a node with children u′ and u′′ , then W(u) ∈ Join(W (u′ ), W (u′′ )).

Intuitively, a D-witness-tree is a certificate that the tree decomposition T is accepted by D. One pertinent question is whether one can devise a way of extracting a solution for Π in G from a witness tree.

Definition 10. An abstract membership function is any function of type µ : N× {0, 1}∗ → {0, 1}. We say that v ∈ N is a µ-member of w if µ(v, w) = 1.

Let ν[G, T ] : VG → N(T) be the function that assigns to each vertex v ∈ VG, the child of the node where v is forgotten. We denote this node by ν[G, T ](v). This function is well defined, since in a nice edge-introducing tree decomposition, for each vertex v there is exactly one node u where v is forgotten. We can extract a subset of vertices from a witness tree as follows.

Intuitively, X(G, T ,W, µ) is the set of all vertices v of G that are µ-members of the string assigned by W to the child of the node of T where v is forgotten.

Definition 11. We say that D is solution-preserving if there is an abstract membership function µ such that for each graph G and each nice edge-introducing tree decomposition T accepted by D, the following conditions are satisfied:

1. For each witness tree W of T , the set X(G, T ,W, µ) belongs to SolΠ(G).
2. For each solution X ∈ SolΠ(G), there is a witness tree W such that X = X(G, T , W, µ).

Intuitively, the first condition implies that if a solution for Π in G exists, then such a solution can be retrieved by backtracking: after inductively constructing the set Γ(u) for each u ∈ N(T), and determining that Γ(r(T)) is non-empty, we may construct a witness-tree W by backtracking and then apply the membership function to the string associated with the child of each forget node to extract a solution. On the other hand, Condition 2 ensures that each solution in SolΠ(G) can be retrieved from some suitable witness-tree.

Definition 12. Let G be a graph, T = (T,B, ξ) be a tree decomposition of G, and X ⊆ VG. The characteristic tree of X is the T-shaped term χ[G, T ,X] where for each u ∈ N(T), χ[G, T ,X](u) = 1 if there is some v ∈ X with ν[G, T ](v) = u, and χ[G, T , X](u) = 0, otherwise.

Given a problem Π, and a graph G, we let

be the set of characteristic trees associated with solutions of G. The next theorem establishes a connection between DPcores deciding a problem Π and T-shaped tree automata accepting the set of characteristic trees of solutions of a graph G.

Theorem 13. Let Π be a vertex subset problem and D be a solution-preserving DP-core of table-complexity α(k, n) solving Π. Let G be a graph and T = (T, B, ξ) be a tree decomposition of G of width k. Then, there is a T-shaped tree automaton A of width α(k, n) accepting the tree language ΦΠ(G, T ).

As a direct consequence of Corollary 6 and Theorem 13 we have our main result establishing an upper bound extension complexity in terms of the complexity of a DP-core.

Theorem 14. Let Π be a vertex subset problem and D be a solution-preserving DP-core of table-complexity α(k, n) solving Π. For each n-vertex graph G of treewidth k, the extension complexity of PΠ(G) is at most O(α(k, n) · n).

6 Upper Bounds for Extended Formulations

A wide variety of vertex subset problems can be solved dynamic programming algorithms operating on tree decompositions. In many cases, such algorithms can be formalized using solution-preserving dynamic programming cores. In this section we show how upper bounds on the table-complexity of classical dynamic programming algorithms parameterized by treewidth can be translated into parameterized upper bounds on the extension complexity of polytopes associated with several well studied combinatorial problems on graphs. It turns out that for several of these problems [Lokshtanov et al., 2011] the upper bounds are asymptotically optimal under the exponential time hypothesis (ETH) [Impagliazzo and Paturi, 2001] the strong exponential time hypothesis (SETH) [Impagliazzo and Paturi, 2001], or related conjectures [Calabro et al., 2009; Carmosino et al., 2016].

6.1 Vertex Problems

We say that a vertex subset problem Π has extension complexity f(k, n) on n-vertex graphs of treewidth at most k if for each n-vertex graph G of treewidth at most k, the polytope PΠ(G) has extension complexity at most f (k, n). On the other hand, we say that Π has no extended formulation with g(k, n) inequalities if no polytope P ′ that is an extended formulation of PΠ(G) can be defined with g(k, n) inequalities or less.

Theorem 15. The problem INDEPENDENTSETℓ has extension complexity 2k nO(1) on n-vertex graphs of treewidth at most k. Under ETH, this problem has no extended formulation with 2o(k)nO(1) inequalities.

Let DOMINATINGSETℓ be the problem consisting of all pairs of the form (G, X) where G is a graph and X is a dominating set in G of size at most ℓ. That is, each vertex of G is either in X or connected to some vertex in X.

Theorem16. The problemDOMINATINGSETℓ has extension complexity 3k nO(1) on n-vertex graphs of treewidth at most k. Under ETH, this problem has no extended formulation with 2o(k)nO(1) inequalities.

Interestingly, the two results above show that our general conversion from solution-preserving DP-cores to extended formulations is optimal in general when it comes to the dependency on the table-complexity of the DP-algorithm.

Theorem 17. Under ETH, the complexity O(α(k, n) · n) in Theorem 14 cannot be improved to α(k, n)o(1) · nO(1) .

6.2 Edge Problems

Although we have stated our main theorems in terms of vertex subset problems, analogous results also hold for edge subset problems.

Definition 18 (Edge Subset Problem). An edge subset problem is a subset Π ⊂ GRAPHS × Pfin(N) satisfying the following conditions:

1. X ⊆ EG, and
2. for each graph H isomorphic to G, and each isomorphism ϕ = (ϕ1, ϕ2) from G to H, (H, ϕ2(X)) ∈ Π.

Given an edge subset problem Π, and instance (G,X) of Π, the set of SolΠ(G) of all solutions of G is defined as in Equation 1.

Let HAMILTONIANCYCLE be the edge subset problem consisting of all pairs of the form (G, X) where G is a graph and X is the subset of edges of some Hamiltonian cycle. This problem can be solved by a solution-preserving DP-core of table-complexity 2O(k log k) · nO(1) on n-vertex graphs of treewidth at most k.

Theorem 19. The problem HAMILTONIANCYCLE has extension complexity 2O(k log k) · nO(1) on n-vertex graphs of treewidth at most k. Under ETH, this problem has no extended formulation with 2o(k)nO(1) inequalities.

Interestingly, HAMILTONIANCYCLE has a (non-solutionpreserving) DP-core whose table-complexity, 2O(k) · nO(1) , matches the conditional lower bound. Although we can still extract a linear system of inequalities of size 2O(k) · nO(1) from the specification of this DP-core, not all Hamiltonian cycles in the corresponding graph are guaranteed to occur extremal solutions of this system of inequalities.

Let G be a graph and (A, B) be a partition of the vertex set of G. The cut-set of this partition is the set of all edges with one endpoint in A and another endpoint in B. We let CUTℓ be the edge problem consisting of all pairs of the form (G,X) where G is a graph and X is a cut-set in G of size at least ℓ.

Theorem 20. The problem CUTℓ has extension complexity 2k nO(1) . Under ETH, this problem has no extended formulation with 2o(k)nO(1) inequalities.

6.3 Tuple Problems

Vertex and edge problems may be generalized straightforwardly to the setting where solutions are tuples containing sets of vertices, sets of edges, or both. For example, if a solution is a d-tuple X = (X1,X2, . . . ,Xd) of subsets of vertices, then the vector corresponding to X is the 0/1-matrix ˆX with d rows and |VG| columns where for each i ∈ [d] and v ∈ VG, ˆXiv = 1 if and only if vertex v belongs to the set Xi. The solution polytope of such a problem is the convex hull of all such matrices. One prominent example of tuple of vertexsubsets problem is the d-COLORING problem, consisting of all pairs of the form (G, (X1, . . . ,Xd)) where G is a graph and (X1, . . . ,Xd) is a partition of the vertex set of G such that each Xi is an independent set in G.

Theorem21. The problem d-COLORING has extension complexity dk nO(1) on n-vertex graphs of treewidth at most k. Under ETH, this problem has no extended formulation with do(k)nO(1) inequalities.

7 Lower Bounds fromEC

Our main theorem states that solution-preserving dynamic programming algorithms with small table-complexity can be translated into extended formulations with a small number of inequalities. Interestingly, this translation allows us to obtain unconditional lower bounds on the table-complexity of solution-preserving DP-cores for a given problem from unconditional lower bounds obtained in the context of the theory of extended formulations. For instance, it has been shown in [G¨o¨os et al., 2018b] that there is a suitable sequence of graphs {Gn}n∈N and suitable ℓ(n) ∈ O(n) such that for each n ∈ N, the graph Gn has n vertices and the solution polytope of the problem INDEPENDENTSETℓ(n) has extension complexity 2Ω(n/ log n) on Gn. This implies the following unconditional parameterized lower bound on the table-complexity of solution-preserving DP-cores solving the independent set problem.

Theorem 22. The problem INDEPENDENTSETℓ has no solution-preserving DP-core of table-complexity 2o(k/logk) · nO(1) on n-vertex graphs of treewidth at most k.

8 Conclusion

In this work, we introduced a general framework to obtain parameterized upper bounds on the extension complexity of the solution polytopes of a wide variety of combinatorial problems in terms of the table-complexity of solution-preserving dynamic programming algorithms. In many cases, the extension complexity obtained using our method is the best one can get (under ETH).

Nevertheless, for some combinatorial problems, such as HAMILTONIANCYCLE and other connectivity problems, the fastest known dynamic programming algorithm parameterized by treewidth [Bodlaender et al., 2015] is not solution preserving. In these cases, our result still yields a polytope associated with the convex-hull of all solutions that can be retrieved by backtracking from the DP tables constructed by the algorithm. The crucial difference is that this polytope does not depend only on the graph, but also on the input tree decomposition and on the particularities of the DP-core.

Another point that is worth mentioning is that our upper bounds on the extension complexity of polytopes in terms of the table-complexity of DP-cores does not depend on the actual computational complexity of constructing the tables. Only the table sizes matter. In this sense, it is not possible to generalize our results to arbitrary non-solution preserving DP-cores without making further assumptions. The reason is that any vertex subset problem has a trivial (non-solution preserving) DP-core of table-complexity 1. This DP-core non-deterministically guesses a solution, and when processing each node, keeps only the partial solution corresponding to the restriction of the guessed solution to vertices belonging to bags up to that node.

Acknowledgments

We acknowledge support from the Research Council of Norway (grant numbers 326537 and 288761).