Dynamic Programming on Tree Decompositions

Section 5.2 Dynamic Programming on Tree Decompositions

Recall that a tree \(T\) is a connected graph without cycles; equivalently, it is a connected graph with \(|V(T)|-1\) edges, or, equivalently, a graph in which there is a unique path between any two vertices. In this section, we continue our discussion of dynamic programming by showing how it can be used to solve some notorious NP-hard graph theory problems on graphs that are “sufficiently tree-like.” Let us clarify what we mean by this. Given a set \(X\text{,}\) let \(2^X\) denote the collection of all subsets of \(X\text{.}\)

Definition 5.2.1. Tree Decomposition.

A tree decomposition of a graph \(G\) is a pair \((T,B)\) where \(T\) is a tree and \(B:V(T)\to 2^{V(G)}\) such that

if \(uv\in E(G)\text{,}\) then there exists \(t\in V(T)\) such that \(u,v\in B(t)\) and
for any \(v\in V(G)\text{,}\) the subgraph \(T_v\) of \(T\) induced by \(\{t: v\in B(t)\}\) is a subtree of \(T\text{.}\)

For \(t\in V(T)\text{,}\) we call \(B(t)\) the bag corresponding to \(t\text{.}\)

Definition 5.2.2. Treewidth.

The width of a tree decomposition \((T,B)\) is defined to be \(\max_{t\in V(T)}\left(|B(t)|-1\right)\text{.}\) The treewidth of a graph \(G\text{,}\) denoted \(\tw(G)\text{,}\) is the minimum width of a tree decomposition of \(G\text{.}\)

It is not hard to see that a graph \(G\) has treewidth equal to \(1\) if and only if it is a forest (i.e. a disjoint union of trees) with at least one edge. It is also a nice exercise to show that a graph containing a clique on \(k\) vertices has treewidth at least \(k-1\text{;}\) see Exercise 5.

Now, we come to a key question: How do tree decompositions of low width help us to solve algorithmic problems? Suppose that \(k\) is a fixed constant and that \(G\) is a graph and that \((T,B)\) is a tree decomposition of \(G\) of width at most \(k\text{.}\) One key observation is that, since \(k\) is fixed, whenever we are dealing with vertices belonging to only a single bag of the tree decomposition, we are free to run a brute force algorithm to compute parameters which pertain to that bag only. For example, we can find all of the possible stable sets among vertices in that bag, generate all of the possible \(3\)-colourings of vertices in that bag, etc, since these problems can be solved in an amount of time that depends only on \(k\) (a fixed constant). So, the rough idea of how we apply dynamic programming to graphs of bounded treewidth is that we compute various parameters of interest in the corresponding bags in a brute-force manner, and then, at each non-leaf vertex \(t\) of the tree, we compute data related to every possible way of “extending” a solution from the bags corresponding to the children of \(t\) (we view the tree as rooted) up to the bag corresponding to \(t\text{.}\) This description is pretty vague, so let’s just try to illustrate it by proving a theorem.

Theorem 5.2.3.

Let \(k\) be a fixed integer. For any graph \(G\text{,}\) weight function \(c:V(G)\to\mathbb{R}\) and tree decomposition \((T,B)\) of \(G\) of width at most \(k\text{,}\) a maximum weight stable set can be found in time \(O(|V(G)|)\text{.}\)

Proof.

It is not hard to show that, for any graph \(G\) and tree decomposition \((T,B)\) of \(G\text{,}\) there exists a tree decomposition \((T',B')\) of \(G\) with \(|V(T')|\leq |V(G)|\) of the same width as \((T,B)\text{.}\) So, we assume that \((T,B)\) satisfies \(|V(T)|\leq |V(G)|\text{.}\) Let \(r\) be an arbitrary root of \(T\) and orient all edges of \(T\) away from \(r\text{.}\) The out-neighbours of a vertex \(x\) in \(T\) are called the children of \(x\) and the vertices that are reachable by directed paths starting at \(x\) are its descendants. The subtree rooted at \(x\) is the subtree of \(T\) induced by \(x\) and all of its descendants.

Now, for each pair \((x,S)\) where \(x\in V(T)\) and \(S\subseteq B(x)\text{,}\) initialize \(mw(x,S):=\text{null}\text{.}\) Here, the letters \(mw\) stand for “max weight;” it will correspond to the highest weight of a stable set containing \(S\) in the subgraph of \(G\) induced by the vertices in the bags in the subtree rooted at \(x\text{.}\) Also, for each arc \(xy\) of \(T\) and set \(S\subseteq B(x)\text{,}\) initialize \(be(xy,S):=\text{null}\text{.}\) Here, \(be\) stands for “best extension” and will describe the intersection of \(B(y)\) with a highest weight stable set containing \(S\) in the subgraph of \(G\) induced by the vertices in the bags in the subtree rooted at \(x\text{.}\) This will play the role of the predecessor function in the previous section and will allow us to construct the maximum weight stable set in the end. Note that, since each bag has cardinality at most \(k+1\) and \(|V(T)|\leq |V(G)|\text{,}\) the domains of the functions \(mw\) and \(be\) each have cardinality at most \(2^{k+1}|V(G)|\text{.}\) Now, to solve the problem, we run the algorithm \(\text{SubtreeStableSet}(r,mw,be)\text{,}\) which is described below in the more general case where \(r\) is replaced by any vertex \(x\) of the tree.

Algorithm 5.2.4. \(\text{SubtreeStableSet}(x,mw,be)\).

if \(x\) is a leaf of \(T\)
- For each \(S\subseteq B(t)\text{,}\) if \(S\) is not a stable set, set \(mw(S)=-\infty\text{.}\) Otherwise, set \(mw(S)\) to be \(w(S)\text{.}\)
if \(x\) is not a leaf of \(T\)
- For each \(y\in N^+(v)\text{,}\) run \(\text{SubtreeStableSet}(y,mw,be)\text{.}\)
- For each set \(S\subseteq B(x)\text{,}\) we do the following.
  - If \(S\) is not a stable set, simply set \(mw(S)=-\infty\) and set \(be(xy,S)=\text{n/a}\) for all children \(y\) of \(x\) in \(T\text{.}\)
  - Otherwise, for each child \(y\) of \(x\) in \(T\text{,}\) choose \(S_y\subseteq B(y)\) in such a way that \(S\cap B(y)=S_y\cap B(x)\) and
    
    \begin{equation*} mw(S_y) - w(S_y\cap S) \end{equation*}
    
    is maximized. Set
    
    \begin{equation*} mw(x,S):=\sum_{y\in N^+(x)}(mw(S_y) - w(S_y\cap S))+w(S) \end{equation*}
    
    and let \(be(xy,S):=S_y\) for every child \(y\) of \(x\text{.}\)

Since the bags have size at most \(k+1=O(1)\text{,}\) the number of steps of this algorithm that involve any given vertex or arc of the tree take time \(O(1)\text{.}\) So, the total running time is \(O(|V(T)|)=O(|V(G)|)\text{.}\)

We claim that, after running this algorithm at the root \(r\text{,}\) we now have enough information to find the maximum weight stable set in the graph. Indeed, let \(S_r\) be the subset of \(B(r)\) for which \(mw(r,S)\) is maximized. Then, for each arc \(xy\) of the tree, starting at the top, we define \(S_y=be(xy,S_x)\text{.}\) After doing this for all arcs, we let

\begin{equation*} S:=\bigcup_{x\in V(T)}S_x. \end{equation*}

We claim that \(S\) is a maximum weight stable set. First, let us explain why it is a stable set. Suppose there is an adjacent pair \(u,v\in S\text{.}\) Let \(x,y\in V(T)\) such that \(u\in S_x\) and \(v\in S_y\) and let \(z\) be the most recent common ancestor of \(x\) and \(y\text{.}\) Since the subtrees \(T_u\) and \(T_v\) must intersect and the unique path from \(x\) to \(y\) in \(T\) passes through \(z\text{,}\) we must have that \(u,v\in B(z)\text{.}\) Also, by construction, the stable sets corresponding to adjacent vertices \(a,b\) of the tree must agree on all of the vertices that are common to the two bags (i.e. if \(w\in B(a)\cap B(b)\text{,}\) then either \(w\in S_a\cap S_b\) or \(w\notin S_a\cup S_b\)). By following along a path from \(x\) to \(z\) and a path from \(y\) to \(z\text{,}\) we get that \(u,v\in S_z\text{.}\) However, this cannot happen as \(S_z\) is a stable set for each vertex of the tree, by construction. So, it is a stable set.

Its fairly evident, if you sit and think about it, that, for every \(x\in V(T)\) and \(S\subseteq B(x)\text{,}\) this algorithm identifies the maximum weight of a stable set containing \(S\) in the graph induced by the bags in the subtree rooted at \(x\text{.}\) Its certainly true at the leaves of the tree and, if you think about how the solutions at the children of \(x\) are combined at \(x\text{,}\) its not hard to see that its correct. I may try to explain this better later, but hopefully this explanation suffices for now!

The above theorem is only one example of a problem that can be solved efficiently on graphs of bounded treewidth. Given this, one may wonder: exactly what types of problems can be solved on such graphs? A satisfactory answer to this is given by a result known as Courcelle’s Theorem. As it turns out, every property that is definable in monadic second order logic with edge set quantification (\(\text{MSO}_2\)) This is a mouthful, but what it actually means is fairly simple. Without going into too much detail, a property of graphs is definable in \(\text{MSO}_2\) if there exists a logical statement involving logical symbols, such as \(\land,\lor,\neg,\to,\leftrightarrow\text{,}\) quantifiers \(\forall,\exists\text{,}\) vertices and edges of the graph edges, and sets of vertices and edges of the graph, which evaluates to true if and only if the graph has the property. This is perhaps a vague definition, but this is not a course on logic, and so hopefully it is sufficient for me to just give you a few examples to illustrate it. A standard example is the \(\text{MSO}_2\) formula for 3-colourability:

\begin{equation*} \exists A\subseteq V(G),\exists B\subseteq V(G),\exists C\subseteq V(G), (\forall v\in V(G), (v\in A)\lor (v\in B)\lor (v\in C))\land (\forall u\in V(G), \forall v\in V(G), ((u\in A)\land (v\in B)\to uv\notin E(G))\land((u\in B)\land (v\in B)\to uv\notin E(G))\land ((u\in C)\land (v\in C)\to uv\notin E(G))). \end{equation*}

Here is an \(\text{MSO}_2\) formula that evaluates to true if and only if \(G\) has a clique set of cardinality 100:

\begin{equation*} \exists S\subseteq V(G), (\forall u\in V(G),\forall v\in V(G), (u\in S)\land(v\in S)\to uv\notin E(G))\land \left(\exists v_1,\dots,\exists v_{100}, \bigwedge_{i=1}^{100}(v_i\in S))\land \bigwedge_{1\leq i<j\leq 100}(v_i\neq v_j)\right) \end{equation*}

Anyway, the punchline here is that one can decide whether a graph with a tree decomposition of small width satisfies a given \(\text{MSO}_2\) formula in linear time. There is also a version of this for optimization problems (such as the max weight stable set problem that we discussed earlier in this section).

Theorem 5.2.5. Courcelle’s Theorem.

For every graph property definable in \(\text{MSO}_2\) on graphs, for every fixed \(k\geq1\text{,}\) if \(G\) is a graph and \((T,B)\) is a tree decomposition of \(G\) of width \(k\text{,}\) then it can be decided in time \(O(|V(G)|)\) whether \(G\) satisfies the property.

One final thing to address is the fact that, in this section, we have provided a tree decomposition as part of the “input” of each problem. However, in practice, it is more realistic to be asked to solve a problem on a graph \(G\) without being supplied with a tree decomposition. As it turns out, there exist polynomial-time algorithms (with respect to \(|V(G)|\)) for finding optimal or near-optimal tree decompositions under the assumption that the treewidth of \(G\) is bounded. So, if supplied with a graph with low treewidth, then one could run one of these algorithms to find a tree decomposition and then use that tree decomposition within a dynamic programming algorithm. However, if the treewidth is not bounded, then you are out of luck. Many problems definable in \(\text{MSO}_2\) (like Stable Set, 3-Colourability, etc) are NP-complete, and so there isn’t much hope to solve them efficiently in general (unless \(\text{P}=\text{NP}\)).

Prev Top Next