|
[[Image:Tree decomposition.svg|thumb|240px|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 (mathematics)|graph]] into a [[tree (graph theory)|tree]] that can be used to speed up solving certain problems ondefine the original graph. The '''[[treewidth''']] measuresof the number of graph verticesand mappedspeed ontoup anysolving treecertain nodecomputational inproblems anon optimalthe tree decompositiongraph.
While it is [[NP-hard]] to determine the treewidth of a graph, many [[NP-hard]] combinatorial problems on graphs are solvable in polynomial time when restricted to graphs of bounded treewidth.
In [[machine learning]], tree decompositions are also called '''junction trees''', '''clique trees''', or '''join trees'''; they
play an important role in problems like [[belief propagation|probabilistic inference]], [[constraint satisfaction]], [[query optimization]], and [[matrix decomposition]].
The concept of tree decompositions and treewidth was originally introduced by {{harvs|last=Halin|first=Rudolf|authorlink=Rudolf Halin|year=1976|txt}}. Later it was rediscovered by {{harvs|first1=Neil|last1=Robertson|author1-link=Neil Robertson (mathematician)|first2=Paul|last2=Seymour|author2-link=Paul Seymour (mathematician)|year=1984|txt}} and has since been studied by many other authors.<ref>{{harvtxt|Diestel|2005}} pp.354–355</ref>
==Definition==
==Treewidth==
The ''width'' of a tree decomposition is the size of its largest set ''X''<sub>''i''</sub> 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 (graph theory)|clique]] in the [[chordal graph]] containing ''G'' with the smallest [[maximum clique|clique number]]. The graphs with treewidth at most ''k'' are also called [[partial k-tree|partial ''k''-trees]]. ▼[[File:3x3 grid graph haven.svg|thumb|A [[Bramble (graph theory)|bramble]] of order four in a 3×3 grid graph, the existence of which shows that the graph has treewidth at least 3]]
▲The ''width'' of a tree decomposition is the size of its largest set ''X''<sub>''i''</sub> 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 (graph theory)|clique]] in the [[chordal graph]] containing ''G'' with the smallest [[maximum clique|clique number]]. The graphs with treewidth at most ''k'' are also called [[partial k-tree|partial ''k''-trees]].
It is NP-complete to determine whether a given graph ''G'' has treewidth at most a given variable ''k''.<ref>{{harvtxt|Arnborg|Corneil|Proskurowski|1987}}.</ref>
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.<ref name="b96">{{harvtxt|Bodlaender|1996}}.</ref> The time dependence of this algorithm on ''k'' is exponential.
Treewidth may also be characterized in terms of [[haven (graph theory)|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 {{nowrap|''k'' + 1}} but of no higher order, where a haven of order {{nowrap|''k'' + 1}} is a function ''β'' that maps each set ''X'' of at most ''k'' vertices in ''G'' into one of the connected components of {{nowrap|''G'' \ ''X''}} and that obeys the [[monotonicity]] property that {{nowrap|''β''(''Y'') ⊆ ''β''(''X'')}} whenever {{nowrap|''X'' ⊆ ''Y''.}}
A similar characterization can also be made using [[Bramble (graph theory)|brambles]], sets of connected subgraphs that all touch each other.<ref>{{harvtxt|Seymour|Thomas|1993}}.</ref>
==Graph minors==
[[Image:Partial 3-tree forbidden minors.svg|thumb|Forbidden minors for partial 3-trees]]
For any fixed constant ''k'', the partial ''k''-trees are closed under the operation of [[graph minor]]s, and therefore, by the [[Robertson–Seymour theorem]], this family can be characterized in terms of a finite set of [[forbidden minor]]s. For partial 1-trees (that is, forests), the single forbidden minor is a triangle, and for the partial 2-trees the single forbidden minor is the [[complete graph]] on four vertices. However, the number of forbidden minors increases for larger values of ''k''. For partial 3-trees there are four forbidden minors: the complete graph on five vertices, the [[octahedron|octahedral graph]] with six vertices, the eight-vertex [[Wagner graph]], and the [[pentagonal prism]] with ten vertices.<ref name="b98">{{harvtxt|Bodlaender|1998}}.</ref>
The [[planar graph]]s do not have bounded treewidth, because the ''n'' × ''n'' [[grid graph]] is a planar graph with treewidth ''n''. Therefore, if ''F'' is a minor-closed graph family with bounded treewidth, it cannot include all planar graphs. Conversely, if some planar graph cannot occur as a minor for graphs in family ''F'', then there is a constant ''k'' such that all graphs in ''F'' have treewidth at most ''k''. That is, the following three conditions are equivalent to each other:<ref>{{harvtxt|Robertson|Seymour|1986}}.</ref>
#''F'' is a minor-closed family of bounded-treewidth graphs;
#One of the finitely many forbidden minors characterizing ''F'' is planar;
#''F'' is a minor-closed graph family that does not include all planar graphs.
Families of graphs with bounded treewidth include the [[cactus graph]]s, [[pseudoforest]]s, [[series-parallel graph]]s, [[outerplanar graph]]s, [[Halin graph]]s, and [[Apollonian network]]s.<ref name="b98"/> The [[control flow graph]]s arising in the [[compiler|compilation]] of [[Structured programming|structured programs]] also have bounded treewidth, which allows certain tasks such as [[register allocation]] to be performed efficiently on them.<ref>{{harvtxt|Thorup|1998}}.</ref>
==Dynamic programming==
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 [[approximation algorithm|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"/>
==Treewidth of cliques==
In any tree decomposition <math>(T, X)</math> of a graph containing a [[Clique (graph theory)|clique]] there is a node ''i'' in ''T'' such that <math>X_i</math> contains all the nodes of the clique. This is shown by [[mathematical induction|induction]] on the size of the clique. The base cases are cliques of size 1 and 2, which follow from the conditions 1 and 2 on a tree decomposition. The inductive case is a graph containing a clique of size ''k''+1, where ''k'' is 2 or greater. Let ''C'' be the set of nodes in the clique. Since <math>k+1 \geq 3</math>, there are at least three nodes in the clique, call them ''x'', ''y'' and ''z''. We know from the induction hypothesis that there are nodes ''a'', ''b'' and ''c'' in the tree decomposition with
:<math>X_a \supseteq C-\{x\}</math>, <math>X_b \supseteq C-\{y\}</math>, <math>X_c \supseteq C-\{z\}</math>.
In a [[Tree (graph theory)|tree]] there is exactly one path between any two nodes. A second property of trees is that the three paths between a, b and c have a non-empty intersection. Let v be a node in this intersection. From condition 3 on a tree decomposition we get that
:<math>X_v \supseteq X_a \cap X_b \supseteq C - \{ x, y \}</math>
:<math>X_v \supseteq X_b \cap X_c \supseteq C - \{ y, z \}</math>
:<math>X_v \supseteq X_a \cap X_c \supseteq C - \{ x, z \}</math>
This implies that <math>X_v \supseteq C</math>.
It follows from this that the treewidth of a ''k''-clique is ''k''-1.
==Treewidth of trees==
A connected graph with at least two vertices has treewidth 1 if and only if it is a tree. This can be shown in two steps, first that a tree has treewidth 1, second, that a connected graph with treewidth 1 is a tree.
To show the former, use [[mathematical induction|induction]] on the number of vertices in the tree to show that it has a tree decomposition with no bag with size larger than two. The base case is a tree with two vertices, in which case the tree decomposition with one single node is sufficient. The inductive case is a tree <math>G</math> with <math>k+1</math> vertices, where <math>k</math> is any integer greater than <math>1</math>. If we remove a [[leaf]] <math>v</math> from the graph, we get a tree of size <math>k</math>. From the induction hypothesis we can create a tree decomposition <math>(T, X)</math> of width 1 of this graph. Let <math>u</math> be the unique neighbour of <math>v</math> in <math>G</math> and <math>i</math> some node in <math>T</math> such that <math>u</math> is in <math>X_i</math>. Let <math>T_1</math> be <math>T</math> added a node <math>j</math> with <math>i</math> as its only neighbour and let <math>X'</math> be <math>X</math> with the addition that <math>X'_j = \{ i, j \} </math>. Now <math>(T_1, X')</math> is a tree decomposition of <math>G</math> with width 1.
Now it remains to show that a connected graph with treewidth 1 is a tree. The [[contrapositive]] statement is that a graph with a cycle does not have treewidth 1. A graph with a cycle has the 3-clique as a minor, which from the statement in the previous section has treewidth 2. Since the partial 2-trees are closed under minors, the graph therefore has treewidth 2 or greater.
==See also==
*[[Clique-width]]
*[[Branch-decomposition]], a closely related structure whose width is within a constant factor of treewidth
*[[Path decomposition]], a tree decomposition in which the underlying tree of the decomposition is a [[path graph]]
*[[Tree-depth]], a number that is bounded for a minor-closed graph family if and only if the family excludes a path
*[[Degeneracy (graph theory)|Degeneracy]], a measure of the sparsity of a graph that is at most equal to its treewidth
==Notes==
| journal = Journal of Algorithms
| volume = 8 | issue = 2 | year = 1987 | pages = 216–235 | doi = 10.1016/0196-6774(87)90039-3}}.
*{{citation
| last1 = Bertelé | first1 = Umberto
| last2 = Brioschi | first2 = Francesco
| title = Nonserial Dynamic Programming
| year = 1972
| publisher = Academic Press
| isbn = 0-12-093450-7}}.
*{{citation
| last = Bodlaender | first = Hans L. | authorlink = Hans L. Bodlaender
| journal = SIAM Journal on Computing
| volume = 25 | issue = 6 | year = 1996 | pages = 1305–1317 | doi = 10.1137/S0097539793251219}}.
*{{citation
| last = Bodlaender | first = Hans L. | authorlink = Hans L. Bodlaender
| title = A partial ''k''-arboretum of graphs with bounded treewidth
| journal = Theoretical Computer Science
| volume = 209 | issue = 1–2 | pages = 1–45 | year = 1998 | doi = 10.1016/S0304-3975(97)00228-4}}.
*{{Citation
| last=Diestel | first=Reinhard
| issue = 1 | year = 1984 | pages = 49–64
| doi = 10.1016/0095-8956(84)90013-3}}.
*{{citation
| last1 = Robertson | first1 = Neil | authorlink1 = Neil Robertson (mathematician)
| last2 = Seymour | first2 = Paul D. | authorlink2 = Paul Seymour (mathematician)
| title = Graph minors V: Excluding a planar graph
| journal = Journal of Combinatorial Theory, Series B
| volume = 41 | issue = 1 | year = 1986 | pages = 92–114 | doi = 10.1016/0095-8956(86)90030-4}}.
*{{citation
| last1 = Seymour | first1 = Paul D. | authorlink1 = Paul Seymour (mathematician)
| last2 = Thomas | first2 = Robin | author2-link=Robin Thomas (mathematician)
| title = Graph Searching and a Min-Max Theorem for Tree-Width.
| journal = Journal of Combinatorial Theory, Series B
| volume = 58 | issue = 1 | pages = 22–33 | doi = 10.1006/jctb.1993.1027
| year = 1993}}.
*{{citation
| last = Thorup | first = Mikkel | authorlink = Mikkel Thorup
| title = All structured programs have small tree width and good register allocation
| journal = Information and Computation
| volume = 142 | issue = 2 | year = 1998 | pages = 159–181 | doi = 10.1006/inco.1997.2697}}.
{{refend}}
[[Category:Trees (graph theory)]]
[[Category:Graph operations]] ▼[[Category:Graph minor theory]]
▲[[Category:Graph operationstheory objects]]
[[cs:Stromový rozklad]]
[[de:Baumweite]]
[[fr:Décomposition arborescente]]
| 