Tree decomposition

From Wikipedia, the free encyclopedia

In graph theory, a tree decomposition is a mapping of a graph into a tree that can be used to speed up solving certain problems on the original graph. The tree resulting from such a conversion has sets of vertices of the graph as its nodes. (To avoid confusion, we refer to vertices of the resulting tree as nodes.)

Given a graph G = (V,E), a tree decomposition is a pair (X,T), where X=\{X_1,\ldots,X_n\} is a family of subsets of V, and T is a tree whose nodes are the subsets Xi, such that:

  1. the union of all X_i \in X equals V;
  2. for every edge (v, w) \in E, there is a node Xi that contains both v and w;
  3. if Xi and Xj both contain a vertex v, then all nodes Xz of the tree in the (unique) path between Xi and Xj contain v.

The last condition is equivalent to saying that all nodes Xi of the tree T containing a vertex v of G induce a subtree of T.

The width of a tree decomposition is the size of its largest set Xi minus one. The tree decomposition is far from unique; for example, a trivial tree decomposition contains all vertices of the graph in its single root node. The treewidth tw(G) of a graph G is the minimum width among all possible tree decompositions of G.

The minus one in the definition is introduced in order to make the treewidth of a tree equal to one.

A graph containing a cycle has treewidth at least two and a graph having the complete graph on four nodes as a minor has treewidth at least three.

While it is NP-hard to determine the treewidth of a graph, many NP-hard problems are also solvable in polynomial time when restricted to graphs of bounded treewidth. Tree decompositions of small width are used to solve combinatorial problems on graphs with dynamic programming.

This combinatorics-related article is a stub. You can help Wikipedia by expanding it.
Retrieved from "http://en.wikipedia.org../../../t/r/e/Tree_decomposition.html"
In other languages