Tree decomposition

Template:Short description Template:About

A graph with eight vertices, and a tree decomposition of it onto a tree with six nodes. Each graph edge connects two vertices that are listed together at some tree node, and each graph vertex is listed at the nodes of a contiguous subtree of the tree. Each tree node lists at most three vertices, so the width of this decomposition is two.

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,Template:Sfnp and matrix decomposition.

The concept of tree decomposition was originally introduced by Template:Harvs. Later it was rediscovered by Template:Harvs and has since been studied by many other authors.<ref>Template:Harvtxt pp.354–355</ref>

DefinitionEdit

Intuitively, a tree decomposition represents the vertices of a given graph Template:Mvar as subtrees of a tree, in such a way that vertices in Template:Mvar are adjacent only when the corresponding subtrees intersect. Thus, Template:Mvar 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 Template:Math, a tree decomposition is a pair Template:Math, where Template:Math is a family of subsets (sometimes called bags) of Template:Mvar, and Template:Mvar is a tree whose nodes are the subsets Template:Mvar, satisfying the following properties:<ref>Template:Harvtxt section 12.3</ref>

The union of all sets Template:Mvar equals Template:Mvar. That is, each graph vertex is associated with at least one tree node.
For every edge Template:Math in the graph, there is a subset Template:Mvar that contains both Template:Mvar and Template:Mvar. That is, vertices are adjacent in the graph only when the corresponding subtrees have a node in common.
If Template:Mvar and Template:Mvar both contain a vertex Template:Mvar, then all nodes Template:Mvar of the tree in the (unique) path between Template:Mvar and Template:Mvar contain Template:Mvar as well. That is, the nodes associated with vertex Template:Mvar form a connected subset of Template:Mvar. This is also known as coherence, or the running intersection property. It can be stated equivalently that if Template:Mvar, Template:Mvar and Template:Mvar are nodes, and Template:Mvar is on the path from Template:Mvar to Template:Mvar, then <math>X_i \cap X_j \subseteq X_k</math>.

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 Template:Math of treewidth Template:Mvar is smooth, if for all <math>i \in I : |X_i| = k + 1</math>, and for all <math>(i, j) \in F : |X_i \cap X_j| = k</math>.<ref name="b96">Template:Harvtxt.</ref>

TreewidthEdit

{{#invoke:Labelled list hatnote|labelledList|Main article|Main articles|Main page|Main pages}}

File:Treedecompsnocolour.JPG

Two different tree-decompositions of the same graph

The width of a tree decomposition is the size of its largest set Template:Mvar minus one. The treewidth Template:Math of a graph Template:Mvar is the minimum width among all possible tree decompositions of Template:Mvar. 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 Template:Mvar has treewidth at most a given variable Template:Mvar.<ref>Template:Harvtxt.</ref> However, when Template:Mvar is any fixed constant, the graphs with treewidth Template:Mvar can be recognized, and a width Template:Mvar tree decomposition constructed for them, in linear time.<ref name="b96"/> The time dependence of this algorithm on Template:Mvar is an exponential function of Template:Math.

Dynamic programmingEdit

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,Template:Sfnp a parameter related to treewidth. Later, several authors independently observed, at the end of the 1980s,<ref>Template:Harvtxt; Template:Harvtxt; Template:Harvtxt.</ref> 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 Template:Mvar. To solve this problem, first choose one of the nodes of the tree decomposition to be the root, arbitrarily. For a node Template:Mvar of the tree decomposition, let Template:Mvar be the union of the sets Template:Mvar descending from Template:Mvar. For an independent set <math>S \subset X_i,</math> let Template:Math denote the size of the largest independent subset Template:Mvar of Template:Mvar such that <math>I \cap X_i = S.</math> Similarly, for an adjacent pair of nodes Template:Mvar and Template:Mvar, with Template:Mvar farther from the root of the tree than Template:Mvar, and an independent set <math>S \subset X_i \cap X_j,</math> let Template:Math denote the size of the largest independent subset Template:Mvar of Template:Mvar such that <math>I \cap X_i \cap X_j = S.</math> We may calculate these Template:Mvar and Template:Mvar values by a bottom-up traversal of the tree:

<math>A(S,i)=|S| + \sum_{j} \left(B(S\cap X_j, j,i) - |S\cap X_j|\right)</math>

<math>B(S,i,j)=\max_{S'\subset X_i\atop S=S'\cap X_j} A(S',i)</math>

where the sum in the calculation of <math>A(S,i)</math> is over the children of node Template:Mvar.

At each node or edge, there are at most Template:Math sets Template:Mvar for which we need to calculate these values, so if Template:Mvar is a constant then the whole calculation takes constant time per edge or node. The size of the maximum independent set is the largest value stored at the root node, and the maximum independent set itself can be found (as is standard in dynamic programming algorithms) by backtracking through these stored values starting from this largest value. Thus, in graphs of bounded treewidth, the maximum independent set problem may be solved in linear time. Similar algorithms apply to many other graph problems.

This dynamic programming approach is used in machine learning via the junction tree algorithm for belief propagation in graphs of bounded treewidth. It also plays a key role in algorithms for computing the treewidth and constructing tree decompositions: typically, such algorithms have a first step that approximates the treewidth, constructing a tree decomposition with this approximate width, and then a second step that performs dynamic programming in the approximate tree decomposition to compute the exact value of the treewidth.<ref name="b96"/>

NotesEdit

Template:Reflist

ReferencesEdit

Template:Refbegin

Template:Refend