# Practical Access to Dynamic Programming on Tree Decompositions +
## 2 Preliminaries  
All graphs considered in this paper are undirected, that is, they consist of a set of vertices \(V\) and of a symmetric edge-relation \(E\subseteq V\times V\). We assume the reader to be familiar with basic graph theoretic terminology--see, for instance, [9]. A _tree decomposition_ of a graph \(G=(V,E)\) is a tuple \((T,\iota)\) consisting of a rooted tree \(T\) and a mapping \(\iota\) from nodes of \(T\) to sets of vertices of \(G\) (which we call _bags_) such that (1) for all \(v\in V\) there is a non-empty, connected set \(\{\,x\in V(T)\mid v\in\iota(x)\,\}\), and (2) for every edge \(\{v,w\}\in E\) there is a node \(y\) in \(T\) with \(\{v,w\}\subseteq\iota(y)\). The _width_ of a tree decomposition is the maximum size of one of its bags minus one, and the _treewidth_ of \(G\), denoted by \(\operatorname{tw}(G)\), is the minimum width any tree decomposition of \(G\) must have. In order to describe dynamic programs over tree decompositions, it turns out be helpful to transform a tree decomposition into a more structured one. A _nice tree decomposition_ is a triple \((T,\iota,\eta)\) where \((T,\iota)\) is a tree decomposition and \(\eta\colon V(T)\to\{\text{leaf},\text{introduce},\text{forget},\text{join}\}\) is a labeling such that (1) nodes labeled \"leaf\" are exactly the leaves of \(T\), and the bags of these nodes are empty; (2) nodes \(n\) labeled \"introduce\" or \"forget\" have exactly one child \(m\) such that there is exactly one vertex \(v\in V(G)\) with either \(v\
ot\in\iota(m)\) and \(\iota(n)=\iota(m)\cup\{v\}\) or \(v\in\iota(m)\) and \(\iota(n)=\iota(m)\setminus\{v\}\), respectively; (3) nodes \(n\) labeled \"join\" have exactly two children \(x,y\) with \(\iota(n)=\iota(x)=\iota(y)\). A _very nice tree decomposition_ is a nice tree decomposition that also has exactly one node labeled \"edge\" for every \(e\in E(G)\), which virtually introduces the edge \(e\) to the bag--that is, whenever we introduce a vertex, we assume it to be \"isolated\" in the bag until its incident edges are introduced. It is well known that any tree decomposition can efficiently be transformed into a very nice one without increasing its width (essentially, traverse through the tree and \"pull apart\" bags) [1]. Whenever we talk about tree decompositions in the rest of the paper, we actually mean very nice tree decompositions. Notethat this increases the space needed to store the decomposition but only by a small factor of \(O(\operatorname{tw}(G))\). Due to the exponential (in \(\operatorname{tw}(G)\)) space requirement typical for the dynamic programs, this overhead is usually negligible. However, we want to stress that all our interfaces also support \"just\" nice tree decompositions. We assume the reader to be familiar with basic logic terminology and give just a brief overview over the syntax and semantic of monadic second-order logic (MSO)--see, for instance, [10] for a detailed introduction. A _vocabulary_ (or _signature_) \(\tau=(R_{1}^{a_{1}},\dots,R_{n}^{a_{n}})\) is a set of _relational symbols_\(R_{i}\) of arity \(a_{i}\geq 1\). A \(\tau\)_-structure_ is a set \(U\)--called _universe_--together with an _interpretation_\(R_{i}^{U}\subseteq R^{a_{i}}\) of the relational symbols in \(U\). Let \(x_{1},x_{2},\dots\) be a sequence of _first-order variables_ and \(X_{1},X_{2},\dots\) be a sequence of _second-order variables_\(X_{i}\) of arity \(\operatorname{ar}(X_{i})\). The atomic \(\tau\)-formulas are \(x_{i}=x_{j}\) for two first-order variables and \(R(x_{i_{1}},\dots,x_{i_{k}})\), where \(R\) is either a relational symbol or a second-order variable of arity \(k\).