Treewidth

In graph theory, the treewidth of an undirected graph is an integer number which specifies, informally, how far the graph is from being a tree. The smallest treewidth is 1; the graphs with treewidth 1 are exactly the trees and the forests. The graphs with treewidth at most 2 are the series–parallel graphs. The maximal graphs with treewidth exactly k are called k-trees, and the graphs with treewidth at most k are called partial k-trees. Many other well-studied graph families also have bounded treewidth. Treewidth may be formally defined in several equivalent ways: in terms of the size of the largest vertex set in a tree decomposition of the graph, in terms of the size of the largest clique in a chordal completion of the graph, in terms of the maximum order of a haven describing a strategy for a pursuit–evasion game on the graph, or in terms of the maximum order of a bramble, a collection of connected subgraphs that all touch each other. Treewidth is commonly used as a parameter in the parameterized complexity analysis of graph algorithms. Many algorithms that are NP-hard for general graphs, become easier when the treewidth is bounded by a constant. The concept of treewidth was originally introduced by under the name of dimension. It was later rediscovered by , based on properties that it shares with a different graph parameter, the Hadwiger number. Later it was again rediscovered by and has since been studied by many other authors. A tree decomposition of a graph G = (V, E) is a tree T with nodes X_1, ..., X_n, where each X_i is a subset of V, satisfying the following properties (the term node is used to refer to a vertex of T to avoid confusion with vertices of G): The union of all sets X_i equals V. That is, each graph vertex is contained in at least one tree node. If X_i and X_j both contain a vertex v, then all nodes X_k of T in the (unique) path between X_i and X_j contain v as well. Equivalently, the tree nodes containing vertex v form a connected subtree of T. For every edge (v, w) in the graph, there is a subset X_i that contains both v and w.