In graph theory, a tree decomposition is a mapping of a graph into a tree that can be used to define the treewidth of the graph and speed up solving certain computational problems on the graph. Tree decompositions are also called junction trees, clique trees, or join trees. They play an important role in problems like probabilistic inference, constraint satisfaction, query optimization, and matrix decomposition. The concept of tree decomposition was originally introduced by Rudolf Halin (1976). Later it was rediscovered by Neil Robertson and Paul Seymour (1984) and has since been studied by many other authors.
Definition Intuitively, a tree decomposition represents the vertices of a given graph G as subtrees of a tree, in such a way that vertices in G are adjacent only when the corresponding subtrees intersect. Thus, G forms a subgraph of the intersection graph of the subtrees. The full intersection graph is a chordal graph. Each subtree associates a graph vertex with a set of tree nodes. To define this formally, we represent each tree node as the set of vertices associated with it. Thus, given a graph G = (V, E), a tree decomposition is a pair (X, T), where X = {X1, …, Xn} is a family of subsets (sometimes called bags) of V, and T is a tree whose nodes are the subsets Xi, satisfying the following properties:
The union of all sets Xi equals V. That is, each graph vertex is associated with at least one tree node. For every edge (v, w) in the graph, there is a subset Xi that contains both v and w. That is, vertices are adjacent in the graph only when the corresponding subtrees have a node in common. If Xi and Xj both contain a vertex v, then all nodes Xk of the tree in the (unique) path between Xi and Xj contain v as well. That is, the nodes associated with vertex v form a connected subset of T. This is also known as coherence, or the running intersection property. It can be stated equivalently that if Xi, Xj and Xk are nodes, and Xk is on the path from Xi to Xj, then X i ∩ X j ⊆ X k {\displaystyle X_{i}\cap X_{j}\subseteq X_{k}} . The tree decomposition of a graph is far from unique; for example, a trivial tree decomposition contains all vertices of the graph in its single root node. A tree decomposition in which the underlying tree is a path graph is called a path decomposition, and the width parameter derived from these special types of tree decompositions is known as pathwidth. A tree decomposition (X, T = (I, F)) of treewidth k is smooth, if for all i ∈ I : | X i | = k + 1 {\displaystyle i\in I:|X_{i}|=k+1} , and for all ( i , j ) ∈ F : | X i ∩ X j | = k {\displaystyle (i,j)\in F:|X_{i}\cap X_{j}|=k} .
Treewidth
The width of a tree decomposition is the size of its largest set Xi minus one. The treewidth tw(G) of a graph G is the minimum width among all possible tree decompositions of G. In this definition, the size of the largest set is diminished by one in order to make the treewidth of a tree equal to one. Treewidth may also be defined from other structures than tree decompositions, including chordal graphs, brambles, and havens. It is NP-complete to determine whether a given graph G has treewidth at most a given variable k. However, when k is any fixed constant, the graphs with treewidth k can be recognized, and a width k tree decomposition constructed for them, in linear time. The time dependence of this algorithm on k is an exponential function of k3.
Dynamic programming At the beginning of the 1970s, it was observed that a large class of combinatorial optimization problems defined on graphs could be efficiently solved by non-serial dynamic programming as long as the graph had a bounded dimension, a parameter related to treewidth. Later, several authors independently observed, at the end of the 1980s, that many algorithmic problems that are NP-complete for arbitrary graphs may be solved efficiently by dynamic programming for graphs of bounded treewidth, using the tree-decompositions of these graphs. As an example, consider the problem of finding the maximum independent set in a graph of treewidth k. To solve this problem, first choose one of the nodes of the tree decomposition to be the root, arbitrarily. For a node Xi of the tree decomposition, let Di be the union of the sets Xj descending from Xi. For an independent set S ⊂ X i , {\displaystyle S\subset X_{i},} let A(S,i) denote the size of the largest independent subset I of Di such that I ∩ X i = S . {\displaystyle I\cap X_{i}=S.} Similarly, for an adjacent pair of nodes Xi and Xj, with Xi farther from the root of the tree than Xj, and an independent set S ⊂ X i ∩ X j , {\displaystyle S\subset X_{i}\cap X_{j},} let B(S,i,j) denote the size of the largest independent subset I of Di such that I ∩ X i ∩ X j = S . {\displaystyle I\cap X_{i}\cap X_{j}=S.} We may calculate these A and B values by a bottom-up traversal of the tree:
… excerpt ends here. Continue reading the full article.
