Tree width

The tree width is a term from graph theory . It says how "tree-like" a graph is. Since many algorithms run efficiently on trees (or tree decompositions) that do not on general graphs, it is interesting to know the tree width. A related term is path length .

The term was introduced in 1972 by Umberto Bertelè and Francesco Brioschi, independently of Rudolf Halin in 1976 and again independently of Neil Robertson and Paul Seymour in 1984.

Formal definition

A tree decomposition of is a pair , where is a tree and is a family of subsets of the node set of the graph such that: ${\displaystyle G=(V,E)}$ ${\displaystyle (X,T)}$ ${\displaystyle T=(I,F)}$ ${\displaystyle X=\{X_{i}|i\in I\}}$ ${\displaystyle V}$

• ${\displaystyle \bigcup _{i\in I}X_{i}=V}$.
• There is one with for all edges . ${\displaystyle (v,w)\in E}$ ${\displaystyle i\in I}$ ${\displaystyle v,w\in X_{i}}$
• The following applies to all : if there is on the path from to in , then . ${\displaystyle i,j,k\in I}$ ${\displaystyle j}$ ${\displaystyle i}$ ${\displaystyle k}$ ${\displaystyle T}$ ${\displaystyle X_{i}\cap X_{k}\subseteq X_{j}}$

The tree width of the tree decomposition of is defined as and the tree width of a graph is defined as the smallest tree width of all tree decompositions of . ${\displaystyle (X,T)}$ ${\displaystyle G}$ ${\displaystyle \max _{i\in I}|X_{i}|-1}$ ${\displaystyle G}$ ${\displaystyle G}$

Subtracting 1 causes the tree width to be 1 if and only if there is a tree (without this subtraction, trees would have tree width 2). ${\displaystyle G}$ ${\displaystyle G}$

Explanation

We distribute the nodes of G on bags (English: buckets or bags) arranged in a tree, the following rules apply:

• Every knot out is in at least one pocket ${\displaystyle V}$
• The two end nodes of each edge are together in at least one pocket
• For each node , the pockets that contain form a subtree ${\displaystyle v}$ ${\displaystyle v}$

properties

complexity

The decision problem whether for a given graph G and a given variable k the tree width of G is at most k is NP-complete . Graphs with a tree width limited by a constant k can, however, be recognized in linear time. The running time of this algorithm depends linearly on the number of nodes of G and exponentially on k .

Barriers

The following tree widths apply:

• Every tree with at least 2 nodes has a tree width of exactly 1.
• Every circle graph with at least 3 nodes has a tree width of exactly 2.
• A graph without edges (including a tree with 1 node) has a tree width of exactly 0.
• Series-parallel graphs have a tree width of at most 2.
• Halingraphs have a tree width of no more than 3.
• The tree width of planar graphs is not limited by a constant. This becomes clear from the example of the - grid graph . These have a tree width of . The treewidth of planar graphs with but knot has been limited. ${\displaystyle (n\times n)}$ ${\displaystyle n}$ ${\displaystyle n}$ ${\displaystyle 3.182\cdot {\sqrt {n}}}$
• The tree width of a graph is at most 1 smaller than its largest clique .

literature

• Reinhard Diestel: graph theory . 5th edition. Springer-Verlag, Berlin, Heidelberg 2010, ISBN 978-3-96134-004-0 , 10th Minors, pp. 287-330 .
• Frank Gurski, Irene Rothe, Jörg Rothe, Egon Wanke: Exact algorithms for difficult graph problems . Springer-Verlag, Berlin, Heidelberg 2010, ISBN 978-3-642-04499-1 .
• Hans L. Bodlaender: Fixed-Parameter Tractability of Treewidth and Pathwidth . In: Bodlaender HL, Downey R., Fomin FV, Marx D. (Eds.): The Multivariate Algorithmic Revolution and Beyond . LNCS 7370. Springer, Berlin, Heidelberg 2012, ISBN 978-3-642-30890-1 , pp. 196-227 , doi : 10.1007 / 978-3-642-30891-8_12 .

Individual evidence

1. ↑ Bertelè, Brioschi, Nonserial Dynamic Programming, Academic Press 1972, there called Dimension
2. ↑ Halin, S-functions for graphs, J. Geom., 8, 1976, 171-186
3. ^ Robertson, Seymour: Graph minors III: Planar tree-width, Journal of Combinatorial Theory, Series B, Volume 36, 1984, pp. 49-64
4. ↑ S. Arnborg; D. Corneil; A. Proskurowski: Complexity of finding embeddings in a k-tree. SIAM Journal on Matrix Analysis and Applications, 8 (2) 1987, pp. 277-284
5. ↑ Hans L. Bodlaender: A linear time algorithm for finding tree-decompositions of small treewidth. SIAM Journal on Computing, 25 (6) 1996, pp. 1305-1317
6. ↑ Fedor V. Fomin, Dimitrios M. Thilikos: New upper bounds on the decomposability of planar graphs . In: Journal of Graph Theory . tape 51 , no. 1 , 2006, p. 53–81 , doi : 10.1002 / jgt.20121 .