treewidth

abbr: tw

tags: tree decomposition

functionally equivalent to: branch width, strong inf-coloring number, mm-width

providers: ISGCI, PACE, PACE

Definition: see Graph minors. II. Algorithmic aspects of tree-width by Robertson, Seymour

Treewidth is arguably the most important graph parameter. Intuitively, it describes how close a graph is to a tree.

On this page we cover only an overview of treewidth. For a more comprehensive introduction, we direct the reader to Parameterized Algorithms by Cygan, Fomin, Kowalik, Lokshtanov, Marx, Pilipczuk, Pilipczuk, Saurabh.

Definition

A tree decomposition is a tree $T$ together with a function $\chi$. To distinguish $T$ from $G$ we call $V(G)$ vertices and $V(T)$ nodes. The function $\chi$ maps each node to a set of vertices in $G$. For each node, the set of vertices assigned to it are called a bag. The tree decomposition $(T,\chi)$ has to follow two rules:

1. Each vertex of the graph is in bags that form a (nonempty) connected subtree of $T$.
2. Each edge of the graph has both of its endpoints in some common bag.

A graph has treewidth $k$ if there exists a tree decomposition such that each bag has size at most $k+1$.

Dynamic programming

Structure of the decomposition implies several important properties. The main property is that each bag constitutes a separator. This allows us to design a bottom-up dynamic programming (DP) algorithms over the tree decomposition for many problems. For the DP examples below we assume the reader is comfortable in designing DP bottom-up algorithms on trees for problems like vertex cover, dominating set, weighted independent set, etc.

Though it is possible to design DP over tree decomposition directly we usually simplify the decomposition so that at every step only one simple ’thing’ is happening. Nice tree decomposition can be computed from a tree decomposition in $O(n)$ time and has the following additional properties:

1. Every node has one of types – leaf, introduce vertex, forget vertex, join.
2. The decomposition is rooted in some leaf node.
3. Leaf nodes are empty and childess, except the root which has one child.
4. Introduce vertex node has the same bag as its only child, and adds a new vertex.
5. Forget vertex node has the same bag as its only child, and removes one of the vertices.
6. Join node has exactly the same bag as its two children.

If introduce edge nodes are not present, then an edge is introduced when its second incident vertex is introduced.

Basic DP example

… work in progress

A few brief examples

• vertex cover – state: part of the solution in the bag; value: size of the solution in the subgraph; introduce vertex node tries both options and verifies all present edges are present; forget vertex node does nothing interesting; join node sums the solution minus size of the solution in the bag which was counted twice
• … work in progress

Relations

Results

• 2025 On a tree-based variant of bandwidth and forbidding simple topological minors by Jacob, Lochet, Paul
  • page 38 : treebandwidth upper bounds treewidth by a computable function – [implied through obstructions]
• 2015 Parameterized Algorithms by Cygan, Fomin, Kowalik, Lokshtanov, Marx, Pilipczuk, Pilipczuk, Saurabh
  • treewidth – Very roughly, treewidth captures how similar a graph is to a tree. There are many ways to define ``tree-likeness’’ of a graph; … it appears that the approach most useful from algorithmic and graph theoretical perspectives, is to view tree-likeness of a graph $G$ as the existence of a structural decomposition of $G$ into pieces of bounded size that are connected in a tree-like fashion. This intuitive concept is formalized via the notions of a tree decomposition and the treewidth of a graph; the latter is a quantitative measure of how good a tree decomposition we can possibly obtain.
• 2012 Twin-Cover: Beyond Vertex Cover in Parameterized Algorithmics by Ganian
  • page 263 : graph classes with bounded twin-cover number are not bounded treewidth – There exists graphs with arbitrarily large twin-cover and bounded tree-width and vice-versa.
  • page 263 : graph classes with bounded treewidth are not bounded twin-cover number – There exists graphs with arbitrarily large twin-cover and bounded tree-width and vice-versa.
• 2012 New Width Parameters of Graphs by Vatshelle
  • page 40 : treewidth upper bounds mm-width by a linear function – Theorem 4.2.5. Let $G$ be a graph, then $\frac 13 (tw(G)+1) \le mmw(G) \le \max(brw(G),1) \le tw(G)+1$
  • page 40 : mm-width upper bounds treewidth by a linear function – Theorem 4.2.5. Let $G$ be a graph, then $\frac 13 (tw(G)+1) \le mmw(G) \le \max(brw(G),1) \le tw(G)+1$
• 2010 Comparing 17 graph parameters by Sasák
  • page 17 : graph class complete is not constant treewidth – Theorem 2.2
  • page 17 : graph class grid is not constant treewidth – Theorem 2.4
  • page 49 : carving-width upper bounds treewidth by a linear function – Theorem 5.5 (tw $\prec$ carw) Tree-width is bounded by carving-width.
• 2009 On tree-partition-width by Wood
  • page 2 : tree-partition-width upper bounds treewidth by a linear function – $2twp(G) \ge tw(G)+1$
• 2008 Simulating Quantum Computation by Contracting Tensor Networks by Markov, Shi
  • page 11 : contraction complexity upper bounds treewidth by a linear function – Proposition 4.2. … $cc(G)=tw(G^)$ … Lemma 4.4. $(tw(G) - 1)/2 \le tw(G^) \le \Delta(G)(tw(G) + 1) - 1.$
• 2007 Graph Treewidth and Geometric Thickness Parameters by Dujmovic, Wood
  • page 5 : treewidth upper bounds arboricity by a constant – Proposition 2. The maximum arboricity of a graph in $\mathcal T_k$ (ed: $k$-tree) is $k$; …
  • page 8 : treewidth upper bounds book thickness by a computable function – The maximum book thickness … of a graph $\mathcal T_k$ (ed: $k$-tree) satisfy … $=k$ for $k \le 2$, $=k+1$ for $k \ge 3$.
• 2005 On the relationship between NLC-width and linear NLC-width by Gurski, Wanke
  • page 8 : treewidth upper bounds NLCT-width by a computable function – The results of [23] imply that each graph class of bounded path-width has bounded linear NLC-width and that each graph class of bounded tree-width has bounded NLCT-width.
• 2000 Upper bounds to the clique width of graphs by Courcelle, Olariu
  • page 18 : treewidth upper bounds clique-width by an exponential function – We will prove that for every undirected graph $G$, $cwd(G) \le 2^{twd(G)+1}+1$ …
• 1998 A partial $k$-arboretum of graphs with bounded treewidth by Bodlaender
  • page 4 : pathwidth upper bounds treewidth by a linear function – Lemma 3. (a) For all graphs $G$, $pathwidth(G) \ge treewidth(G)$. …
  • page 34 : outerplanar upper bounds treewidth by a constant – Lemma 78. Every outerplanar graph $G=(V,E)$ has treewidth at most 2.
  • page 37 : graph class grid is not constant treewidth – Lemma 88. The treewidth of an $n \times n$ grid graph … is at least $n$.
  • page 38 : treewidth upper bounds minimum degree by a constant – Lemma 90 (Scheffler [94]). Every graph of treewidth at most $k$ contains a vertex of degree at most $k$.
• 1994 k-NLC graphs and polynomial algorithms by Wanke
  • page 6 : treewidth upper bounds NLC-width by an exponential function – Theorem 2.5. For each partial $k$-tree $G$ there is a $(2^{k+1}-1)$-NLC tree $J$ with $G=unlab(J)$.
• 1993 The Pathwidth and Treewidth of Cographs by Bodlaender, Möhring
  • page 4 : graph class complete is not constant treewidth – Lemma 3.1 (“clique containment lemma”). Let $({X_i\mid u\in I},T=(I,F))$ be a tree-decomposition of $G=(V,E)$ and let $W \subseteq V$ be a clique in $G$. Then there exists $i \in I$ with $W \subseteq X_i$.
  • page 4 : graph class bipartite is not constant treewidth – Lemma 3.2 (“complete bipartite subgraph containment lemma”).
• 1993 On the chordality of a graph by McKee, Scheinerman
  • page 5 : treewidth upper bounds chordality by a constant – Theorem 7. For any graph $G$, $\mathrm{Chord}(G) \le \tau(G)$.
• 1991 Graph minors. X. Obstructions to tree-decomposition by Robertson, Seymour
  • page 16 : treewidth upper bounds branch width by a linear function – (5.1) For any hypergraph $G$, $\max(\beta(G), \gamma(G)) \le \omega(G) + 1 \le \max(\lfloor(3/2)\beta(G)\rfloor, \gamma(G), 1)$.
  • page 16 : branch width upper bounds treewidth by a linear function – (5.1) For any hypergraph $G$, $\max(\beta(G), \gamma(G)) \le \omega(G) + 1 \le \max(\lfloor(3/2)\beta(G)\rfloor, \gamma(G), 1)$.
• 1986 Graph minors. V. Excluding a planar graph by Robertson, Seymour
  • page 2 : excluded planar minor upper bounds treewidth by a constant – (1.5) For every planar graph $H$, there is a number $w$ such that every planar graph with no minor isomorphic to $H$ has tree-wdtih $\le w$
• 1986 Graph minors. II. Algorithmic aspects of tree-width by Robertson, Seymour
  • page 1 : treewidth – A \emph{tree-decomposition} of $G$ is a family $(X_i \colon i\in I)$ of subsets of $V(G)$, together with a tree $T$ with $V(T)=I$, with the following properties. (W1) $\bigcup(X_i \colon i \in I)=V(G)$. (W2) Every edge of $G$ has both its ends in some $X_i$ ($i \in I$). (W3) For $i,j,k \in I$, if $j$ lies on the path of $T$ from $i$ to $k$ then $X_i \cap X_k \subseteq X_j$. The \emph{width} of the tree-decomposition is $\max(|X_i|-1 \colon i \in I)$. The tree-width of $G$ is the minimum $w \ge 0$ such that $G$ has a tree-decomposition of width $\le w$.
  • page 1 : treewidth – Equivalently, the tree-width of $G$ is the minimum $w \ge 0$ such that $G$ is a subgraph of a ``chordal’’ graph with all cliques of size at most $w + 1$.
• assumed
  • degree treewidth upper bounds treewidth by a linear function – by definition
  • treewidth is equivalent to treewidth – assumed
• unknown source
  • strong inf-coloring number upper bounds treewidth by a computable function
  • treewidth upper bounds strong inf-coloring number by a computable function
  • treewidth upper bounds excluded top-minor by a constant
  • distance to outerplanar upper bounds treewidth by a linear function – After removal of $k$ vertices the remaining class has a bounded width $w$. So by including the removed vertices in every bag, we can achieve decomposition of width $w+k$
  • treewidth upper bounds book thickness by a computable function
  • treewidth upper bounds boolean width by a linear function
  • treewidth upper bounds tree-independence number by a computable function
  • overlap treewidth upper bounds treewidth by a computable function
  • treewidth upper bounds sparse twin-width by a tower function