# Chapter 34. Tree Decomposition # Chapter 34. Tree Decomposition A tree decomposition represents a graph by arranging overlapping sets of vertices along a tree. The purpose is to describe a graph that may contain cycles by using a tree-like structure. The graph itself may be complicated, but its vertices are grouped into bags, and the bags are organized as nodes of a tree. If the bags are small, many hard graph problems become easier. Tree decompositions are important in structural graph theory, dynamic programming, constraint satisfaction, probabilistic inference, database query optimization, and algorithms on graphs of bounded treewidth. A standard definition uses three conditions: every graph vertex appears in some bag, every graph edge appears inside some bag, and the bags containing a fixed vertex form a connected subtree. ## 34.1 Motivation Trees are simpler than general graphs. A tree has no cycles. Between any two vertices there is exactly one simple path. Many problems that are hard on general graphs are easy on trees because information can be passed from leaves toward a root. A general graph may contain many cycles. These cycles create dependencies that prevent simple recursive methods. A tree decomposition handles this by grouping vertices into bags. Each bag stores a local part of the graph. The tree structure describes how these local parts are connected. The guiding idea is this: A graph is close to a tree if it can be decomposed into small overlapping pieces arranged as a tree. The size of the largest bag measures how far the graph is from being tree-like. ## 34.2 Definition Let $$ G=(V,E) $$ be an undirected graph. A tree decomposition of \(G\) is a pair $$ (T,\mathcal{B}), $$ where \(T\) is a tree and $$ \mathcal{B}=\{B_t : t \in V(T)\} $$ is a family of subsets of \(V\), one subset for each node \(t\) of \(T\). Each set \(B_t\) is called a bag. The following three conditions must hold. First, every vertex of \(G\) appears in at least one bag: $$ \bigcup_{t \in V(T)} B_t = V. $$ Second, every edge of \(G\) is contained in some bag. That is, for every edge $$ \{u,v\}\in E, $$ there exists a node \(t\in V(T)\) such that $$ u,v \in B_t. $$ Third, for every vertex \(v\in V\), the set of nodes $$ \{t\in V(T): v\in B_t\} $$ forms a connected subtree of \(T\). The third condition is called the connectedness condition or running intersection property. It prevents a vertex from disappearing and then reappearing in unrelated parts of the decomposition. ## 34.3 Bags and the Decomposition Tree There are two graphs involved in a tree decomposition. The original graph is $$ G. $$ Its vertices are the objects we want to study. The decomposition tree is $$ T. $$ Its nodes are not vertices of \(G\). Instead, each node of \(T\) carries a bag, and each bag is a subset of vertices of \(G\). This distinction is important. To avoid confusion, one often says vertex for an element of \(V(G)\), and node for an element of \(V(T)\). A bag may contain one vertex, two vertices, or many vertices. Adjacent bags in \(T\) usually overlap. The overlaps are where information is passed between parts of the decomposition. ## 34.4 A Simple Example Let \(G\) be the path graph $$ 1-2-3-4. $$ One tree decomposition has three bags: $$ B_1=\{1,2\}, $$ $$ B_2=\{2,3\}, $$ $$ B_3=\{3,4\}. $$ Let the decomposition tree be the path $$ B_1-B_2-B_3. $$ Every graph vertex appears in some bag. Every graph edge appears inside a bag: $$ \{1,2\}\subseteq B_1, $$ $$ \{2,3\}\subseteq B_2, $$ $$ \{3,4\}\subseteq B_3. $$ The bags containing vertex \(2\) form the connected set $$ B_1-B_2. $$ The bags containing vertex \(3\) form the connected set $$ B_2-B_3. $$ Vertices \(1\) and \(4\) each appear in one bag. Thus all three conditions hold. This example shows that a tree is already tree-like. Its decomposition can use bags of size \(2\). ## 34.5 A Cycle Example Consider the cycle graph $$ 1-2-3-4-1. $$ This graph is not a tree, but it has a small tree decomposition. Take the bags $$ B_1=\{1,2,4\}, $$ $$ B_2=\{2,3,4\}. $$ Let the decomposition tree consist of one edge: $$ B_1-B_2. $$ Every vertex appears in some bag. The edges are covered: $$ \{1,2\}\subseteq B_1, $$ $$ \{2,3\}\subseteq B_2, $$ $$ \{3,4\}\subseteq B_2, $$ $$ \{4,1\}\subseteq B_1. $$ The bags containing vertex \(2\) are \(B_1\) and \(B_2\), which are adjacent. The bags containing vertex \(4\) are also \(B_1\) and \(B_2\). The other vertices appear once. Thus the cycle has a tree decomposition with bags of size \(3\). The cycle cannot be decomposed with only bags of size \(2\), because a cycle has more dependency than a tree. This difference is measured by treewidth. ## 34.6 Width The width of a tree decomposition is one less than the size of its largest bag: $$ \operatorname{width}(T,\mathcal{B}) = \max_{t\in V(T)} |B_t| - 1. $$ The subtraction by \(1\) is conventional. With this convention, a tree has treewidth \(1\), not \(2\), because it can be decomposed into bags of size \(2\). A decomposition with small width is better for many algorithms, because the amount of local state often grows exponentially in the bag size. For example: | Largest bag size | Width | |---:|---:| | \(1\) | \(0\) | | \(2\) | \(1\) | | \(3\) | \(2\) | | \(k+1\) | \(k\) | ## 34.7 Treewidth The treewidth of a graph \(G\), written $$ \operatorname{tw}(G), $$ is the minimum width over all tree decompositions of \(G\): $$ \operatorname{tw}(G) = \min_{(T,\mathcal{B})} \left( \max_{t\in V(T)} |B_t| - 1 \right). $$ Treewidth measures how close a graph is to a tree. A graph has treewidth \(0\) exactly when it has no edges. A forest has treewidth at most \(1\). Any nonempty forest has treewidth exactly \(1\). A cycle has treewidth \(2\). Complete graphs have large treewidth. For the complete graph \(K_n\), every pair of vertices is adjacent. In any tree decomposition, all \(n\) vertices must appear together in some bag. Therefore $$ \operatorname{tw}(K_n)=n-1. $$ ## 34.8 Why the Connectedness Condition Matters The first two conditions alone are not enough. Suppose a vertex \(v\) appears in two distant bags but not in the bags between them. Then the decomposition treats \(v\) as if it belongs to two separate regions. This breaks dynamic programming, because information about \(v\) could become inconsistent. The connectedness condition ensures that all appearances of \(v\) form one contiguous region of the decomposition tree. If \(v\) appears in bag \(B_a\) and bag \(B_b\), then \(v\) must appear in every bag on the unique path between \(B_a\) and \(B_b\) in \(T\). This condition is what makes the decomposition behave like a coherent tree-structured representation. ## 34.9 Separators from Tree Decompositions Tree decompositions encode separators. Let \(xy\) be an edge of the decomposition tree \(T\). Removing this edge splits \(T\) into two components. These two components correspond to two collections of bags. Let $$ S = B_x \cap B_y. $$ Then \(S\) acts as a separator between the parts of \(G\) represented on the two sides. Any path in \(G\) from a vertex that appears only on one side to a vertex that appears only on the other side must pass through a vertex in \(S\). This separator view explains why tree decompositions support divide-and-conquer algorithms. The graph can be separated into parts that interact through small boundary sets. ## 34.10 Trivial Decomposition Every graph has a tree decomposition. The simplest one uses a single bag: $$ B = V. $$ The decomposition tree has one node carrying this bag. All conditions are immediate. Every vertex appears in the bag. Every edge has both endpoints in the bag. The connectedness condition holds because each vertex appears in a one-node subtree. The width of this decomposition is $$ |V|-1. $$ This decomposition is usually not useful, but it proves that treewidth is always defined for finite graphs. ## 34.11 Tree Decomposition of a Tree Let \(G\) itself be a tree. For every edge $$ \{u,v\}\in E(G), $$ create a bag $$ B_{uv}=\{u,v\}. $$ Arrange these bags in a tree structure corresponding to the original tree. One way is to root \(G\), then connect bags for adjacent edges when the corresponding edges share a vertex and lie next to each other in the rooted structure. Every edge of \(G\) is contained in its own bag. Every vertex \(v\) appears in the bags corresponding to edges incident with \(v\). These bags form a connected subtree. Thus every tree with at least one edge has a decomposition of width \(1\). Since a graph of treewidth \(0\) has no edges, every nontrivial tree has treewidth \(1\). ## 34.12 Complete Graphs Complete graphs have large treewidth. Let $$ G=K_n. $$ In a complete graph, every pair of vertices is adjacent. For any tree decomposition of \(K_n\), there must be a bag containing every vertex of \(K_n\). This follows from the Helly property for subtrees of a tree: if every pair of connected subtrees intersects, then all of them have a common intersection. For each vertex \(v\in V(K_n)\), the bags containing \(v\) form a connected subtree of the decomposition tree. Since every pair of vertices is adjacent, each pair of these subtrees intersects in some bag. Hence all \(n\) subtrees share a common node. The bag at that node contains all vertices. Therefore the largest bag has size at least \(n\), and $$ \operatorname{tw}(K_n)=n-1. $$ ## 34.13 Dynamic Programming on Tree Decompositions Tree decompositions are algorithmically useful because they reduce global graph problems to local computations on bags. A typical dynamic programming algorithm proceeds as follows: 1. Root the decomposition tree. 2. Process bags from leaves toward the root. 3. For each bag, store partial solutions indexed by the vertices in that bag. 4. Combine information from child bags through their intersections with the parent bag. 5. Read the final answer at the root. The running time is often exponential in the treewidth but polynomial in the number of vertices. A common form is $$ O(f(k)n), $$ where \(k\) is the treewidth and \(n=|V|\). The function \(f(k)\) may be exponential, but if \(k\) is small, the algorithm can be efficient. This is the main reason bounded-treewidth graphs are important. ## 34.14 Example: Independent Set An independent set is a set of vertices no two of which are adjacent. On a general graph, finding a maximum independent set is computationally hard. On a graph with small treewidth, it can be solved by dynamic programming over a tree decomposition. For each bag \(B_t\), one considers all subsets $$ S \subseteq B_t. $$ Only subsets that are independent inside the bag are allowed. The algorithm records the best partial solution below \(t\) consistent with choosing \(S\) inside \(B_t\). The number of subsets of a bag is $$ 2^{|B_t|}. $$ Thus small bags make the computation feasible. This illustrates the general pattern: treewidth controls the number of boundary configurations. ## 34.15 Nice Tree Decompositions For algorithmic purposes, tree decompositions are often converted into nice tree decompositions. A nice tree decomposition is rooted and has restricted node types. Common types are: | Node type | Meaning | |---|---| | Leaf | Starts a computation | | Introduce vertex | Adds one vertex to the bag | | Forget vertex | Removes one vertex from the bag | | Introduce edge | Accounts for one graph edge | | Join | Combines two child computations | Nice decompositions simplify dynamic programming because each step changes the bag in a controlled way. They do not change the essential width. They mainly provide a convenient normal form. ## 34.16 Chordal Graph View Tree decompositions are closely related to chordal graphs. A chordal graph is a graph in which every cycle of length at least four has a chord. A chord is an edge connecting two nonconsecutive vertices of the cycle. One may view a tree decomposition as embedding the original graph into a chordal supergraph whose maximal cliques correspond to bags. From this viewpoint, treewidth is one less than the minimum possible clique size in such a chordal completion. This connection links tree decompositions with elimination orderings, sparse matrix factorization, and graphical models. ## 34.17 Elimination Orderings An elimination ordering is an ordering of vertices $$ v_1,v_2,\ldots,v_n. $$ Eliminating a vertex means making its remaining neighbors into a clique, then removing the vertex. The width of an elimination ordering is the maximum number of later neighbors any vertex has at the moment it is eliminated. The treewidth of a graph equals the minimum width over all elimination orderings. This gives another way to understand treewidth. A graph has small treewidth if its vertices can be eliminated while keeping small remaining neighborhoods. ## 34.18 Applications Tree decompositions appear in several areas. | Area | Role of tree decomposition | |---|---| | Graph algorithms | Dynamic programming over bags | | Constraint satisfaction | Variables in bags, constraints across bags | | Probabilistic inference | Junction tree methods | | Database systems | Join trees and acyclic query plans | | Sparse linear algebra | Fill-in and elimination | | Structural graph theory | Measuring tree-like structure | | Logic | Efficient model checking on bounded treewidth | The common theme is controlled interaction. A large structure is decomposed into parts whose overlap is small. ## 34.19 Limitations Tree decompositions are powerful when the width is small. They become less useful when the treewidth is large. A graph may have many vertices but small treewidth, or it may have moderate size and large treewidth. Dense graphs often have large treewidth because many vertices must appear together in bags. Finding an optimal tree decomposition is itself computationally difficult in general. In practice, algorithms often use heuristics or approximation methods to find decompositions that are good enough. Thus tree decomposition is most effective when the input graph has natural sparsity, locality, or separator structure. ## 34.20 Summary A tree decomposition represents a graph by assigning subsets of graph vertices, called bags, to the nodes of a tree. The bags must cover all vertices, cover all edges, and satisfy the connectedness condition for each vertex. The width of a decomposition is the largest bag size minus one. The treewidth of a graph is the minimum possible width. Small treewidth means that the graph is structurally close to a tree. This enables dynamic programming and separator-based reasoning. Tree decompositions therefore form a bridge between graph structure and efficient algorithms.