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. Equivalently, the treewidth of G is one less than the size of the largest clique in the chordal graph containing G with the smallest clique number. The graphs with treewidth at most k are also called partial k-trees.
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 exponential.
Treewidth may also be characterized in terms of havens, functions describing an evasion strategy for a certain pursuit-evasion game defined on a graph. A graph G has treewidth k if and only if it has a haven of order k + 1 but of no higher order, where a haven of order k + 1 is a function β that maps each set X of at most k vertices in G into one of the connected components of G \ X and that obeys the monotonicity property that β(Y) ⊆ β(X) whenever X ⊆ Y. A similar characterization can also be made using brambles, sets of connected subgraphs that all touch each other.
Read more about this topic: Tree Decomposition