# Tree decomposition

A tree decomposition of a graph is a mapping of the graph's vertices into bags arranged on the nodes of a tree, such that every edge of the graph lies inside some bag and the bags containing any one vertex form a connected subtree. The concept was introduced by [Neil Robertson](https://www.edgepedia.org/neil-robertson), professor emeritus at [Ohio State University](https://www.edgepedia.org/ohio-state-university), and [Paul Seymour](https://www.edgepedia.org/paul-seymour-mathematician), professor at Princeton University, in their 1986 paper "Graph minors. II. Algorithmic aspects of tree-width", where they defined the associated invariant treewidth and used it to obtain polynomial-time algorithms for fixed-planar-graph contractibility<sup>[1](https://www.sciencedirect.com/science/article/pii/0196677486900234)</sup>. The width of a decomposition measures how far the graph is from being a tree, and small width is the key that makes many otherwise intractable problems solvable by dynamic programming<sup>[2](https://www.stat.berkeley.edu/~mmahoney/pubs/im_treedecompositions.pdf)</sup>.

| Key fact | Detail |
|---|---|
| Definition | A pair \( (\{X_i\}_{i \in I},\ T=(I,F)) \) with bags \( X_i \subseteq V \) covering \( V \), covering every edge, and with each vertex's bags forming a connected subtree<sup>[2](https://www.stat.berkeley.edu/~mmahoney/pubs/im_treedecompositions.pdf)</sup> |
| Width | \( \max_{i \in I} |X_i| - 1 \); the treewidth \( tw(G) \) is the minimum width over all decompositions<sup>[3](https://courses.csail.mit.edu/6.854/18/Scribe/s25-online/s25-online.html)</sup> |
| Benchmark values | Trees have treewidth 1, cycles 2, an \( n \)-vertex clique \( n-1 \), and the \( n \times n \) planar grid \( n \)<sup>[2](https://www.stat.berkeley.edu/~mmahoney/pubs/im_treedecompositions.pdf)</sup> |
| Clique property | Every complete subgraph of \( G \) is contained in a single bag of any tree decomposition<sup>[2](https://www.stat.berkeley.edu/~mmahoney/pubs/im_treedecompositions.pdf)</sup> |
| Complexity | Deciding whether \( tw(G) \le w \) is NP-complete, but fixed-parameter tractable in \( w \)<sup>[4](https://www.sciencedirect.com/topics/computer-science/tree-decomposition)</sup> |
| Best exact algorithm | \( 2^{O(tw(G)^2)} \cdot n^4 \) time (Korhonen and Lokshtanov, STOC 2023); single-exponential dependence on treewidth remains open<sup>[5](https://arxiv.org/abs/2504.18302)</sup> |
| Main use | Dynamic programming over the bags solves many NP-hard problems in polynomial time on graphs of bounded treewidth<sup>[2](https://www.stat.berkeley.edu/~mmahoney/pubs/im_treedecompositions.pdf)</sup> |

## Definition

For a graph \( G = (V, E) \), a tree decomposition is a tree \( T \) whose nodes \( i \) carry bags \( X_i \subseteq V \) satisfying three conditions<sup>[2](https://www.stat.berkeley.edu/~mmahoney/pubs/im_treedecompositions.pdf)</sup><sup> • </sup><sup>[3](https://courses.csail.mit.edu/6.854/18/Scribe/s25-online/s25-online.html)</sup>:

1. \( \bigcup_{i \in I} X_i = V \): every vertex appears in at least one bag.
2. For every edge \( (v, w) \in E \), some bag contains both \( v \) and \( w \).
3. For every vertex \( v \), the set \( \{ i : v \in X_i \} \) forms a connected subtree of \( T \).

The third condition is a continuity requirement, equivalent to saying that if \( j \) lies on the path from \( i \) to \( k \) in \( T \), then \( X_i \cap X_k \subseteq X_j \). It is what allows the decomposition to be traversed once during a dynamic program, since the bags and their intersections act as separators: removing the vertices of any bag, or of the intersection of two adjacent bags, disconnects the graph<sup>[2](https://www.stat.berkeley.edu/~mmahoney/pubs/im_treedecompositions.pdf)</sup>.

The width of a decomposition is \( \max_{i \in I} |X_i| - 1 \), and the treewidth \( tw(G) \) is the minimum width over all valid decompositions; a decomposition achieving it is called optimal<sup>[2](https://www.stat.berkeley.edu/~mmahoney/pubs/im_treedecompositions.pdf)</sup>. The subtraction of one makes a tree itself have treewidth 1, since its bags contain the two endpoints of each edge<sup>[2](https://www.stat.berkeley.edu/~mmahoney/pubs/im_treedecompositions.pdf)</sup>. Decompositions are not unique even at minimum width<sup>[2](https://www.stat.berkeley.edu/~mmahoney/pubs/im_treedecompositions.pdf)</sup>.

## Examples and basic bounds

The canonical examples span the whole range. A tree has treewidth 1, the minimum possible for a graph with edges. All cycles have treewidth 2, regardless of length: removing a vertex from a cycle and joining its two neighbors leaves a smaller cycle<sup>[3](https://courses.csail.mit.edu/6.854/18/Scribe/s25-online/s25-online.html)</sup>. At the other extreme, an \( n \)-vertex clique has treewidth \( n-1 \), the maximum for an \( n \)-vertex graph, and its only valid decompositions place all vertices in a single bag<sup>[2](https://www.stat.berkeley.edu/~mmahoney/pubs/im_treedecompositions.pdf)</sup>. The \( n \times n \) planar grid has treewidth \( n \), so grids are far from treelike by this measure<sup>[2](https://www.stat.berkeley.edu/~mmahoney/pubs/im_treedecompositions.pdf)</sup>.

Two structural facts follow directly from the definition. Because decompositions remain valid under taking subgraphs, every clique of \( G \) must sit inside some bag of any decomposition<sup>[2](https://www.stat.berkeley.edu/~mmahoney/pubs/im_treedecompositions.pdf)</sup>. And treewidth is bounded above by bandwidth: if vertices can be numbered so adjacent vertices differ by at most \( b \), the sliding windows \( X_i = \{i, \ldots, i+b\} \) form a decomposition of width \( b \)<sup>[6](https://doi.org/10.1016/j.ejc.2009.10.010)</sup>.

Treewidth also has an ordering characterization. An elimination ordering removes vertices one at a time, joining each removed vertex's neighbors; the induced treewidth is the maximum neighborhood size encountered, and \( tw(G) \) is the minimum over all orderings<sup>[3](https://courses.csail.mit.edu/6.854/18/Scribe/s25-online/s25-online.html)</sup>. Equivalently, \( tw(G) \) is the smallest \( w \) such that \( G \) is a subgraph of a chordal graph, a graph in which every cycle of length four or more has a chord, with all cliques of size at most \( w+1 \)<sup>[7](https://vaclavblazej.github.io/parameters/html/i56ihO/)</sup>. A chordal graph itself admits a tree decomposition whose bags are exactly its maximal cliques, called a clique tree<sup>[8](https://web.math.princeton.edu/~pds/papers/containers/paper.pdf)</sup>.

## Origin in the Graph Minors project

Robertson and Seymour introduced treewidth and tree decompositions in "Graph minors. II. Algorithmic aspects of tree-width" (Journal of Algorithms, volume 7, issue 3, pages 309–322, 1986)<sup>[1](https://www.sciencedirect.com/science/article/pii/0196677486900234)</sup>. That paper used the invariant to test, in polynomially bounded time, whether a graph has a subgraph contractible to any fixed planar graph \( H \), and gave a nonconstructive proof that testing \( tw(G) \le w \) for fixed \( w \) is polynomial; the authors noted that neither algorithm was practical because the polynomial exponents were large<sup>[1](https://www.sciencedirect.com/science/article/pii/0196677486900234)</sup>.

The companion paper "Graph minors. X. Obstructions to tree-decomposition" ([Journal of Combinatorial Theory](https://www.edgepedia.org/journal-of-combinatorial-theory), Series B, volume 52, issue 2, pages 153–190, 1991) studied what prevents small treewidth. It established a minimax formula relating treewidth to the largest obstructions, an association between these obstructions and large grid minors of the graph, and a tree decomposition of the graph into pieces corresponding to the obstructions<sup>[9](https://www.sciencedirect.com/science/article/pii/009589569190061N)</sup>. In this sense grids are essentially the only obstruction to bounded treewidth<sup>[2](https://www.stat.berkeley.edu/~mmahoney/pubs/im_treedecompositions.pdf)</sup>.

## Computing decompositions

Finding a decomposition of minimum width is NP-hard<sup>[2](https://www.stat.berkeley.edu/~mmahoney/pubs/im_treedecompositions.pdf)</sup>, and deciding whether \( tw(G) \le w \) is NP-complete<sup>[4](https://www.sciencedirect.com/topics/computer-science/tree-decomposition)</sup>. For fixed \( w \), the first polynomial-time algorithm was due to Arnborg, Corneil, and Proskurowski, and the problem is fixed-parameter tractable: tractable in \( f(w) \cdot n^{O(1)} \) time for a function \( f \) of the width alone. Robertson and Seymour established this fixed-parameter tractability nonconstructively in the Graph Minors project, and in 1996 Hans Bodlaender, professor at [Utrecht University](https://www.edgepedia.org/utrecht-university), published a constructive algorithm that decides whether \( tw(G) \le w \) and, if so, builds a decomposition of width at most \( w \)<sup>[4](https://www.sciencedirect.com/topics/computer-science/tree-decomposition)</sup>.

The exact running times have improved steadily. A factor-5 approximation can be computed in \( \exp(k) \cdot n \) time (Bodlaender, Drange, Dregi, Fomin, Lokshtanov, and Pilipczuk, 2013), and it is unknown whether the problem has a polynomial-time approximation scheme<sup>[10](https://pacechallenge.org/2016/09/12/results-PACE-2016/)</sup>. A 2024 paper by Mahdi Belbasi, Martin Fürer, and Medha Kumar gives a linear fixed-parameter algorithm producing a 2-approximation with a smaller exponential dependence on the treewidth than previously known<sup>[11](https://arxiv.org/abs/2411.16918)</sup>. For exact computation, the best known algorithm, by Korhonen and Lokshtanov (STOC 2023), runs in \( 2^{O(tw(G)^2)} \cdot n^4 \) time; whether an optimal decomposition can be computed in single-exponential time in the treewidth is one of the open problems of parameterized complexity<sup>[5](https://arxiv.org/abs/2504.18302)</sup>.

In practice, upper-bound heuristics dominate. Bodlaender and Arie M. C. A. Koster, then at [RWTH Aachen University](https://www.edgepedia.org/rwth-aachen-university), surveyed heuristics that produce decompositions whose width is not necessarily optimal but that experiments show often come close to the exact treewidth<sup>[12](https://www.researchgate.net/publication/266549721_Treewidth_computations_I_Upper_bounds)</sup>. Because heuristics are fast compared with the dynamic programming that consumes the decomposition, running several heuristics and keeping the smallest-width result is a common strategy<sup>[4](https://www.sciencedirect.com/topics/computer-science/tree-decomposition)</sup>. The PACE (Parameterized Algorithms and Computational Experiments) challenge made implementation quality a public competition: its 2016 edition, the first, ran exact and heuristic tracks for treewidth, with the winning exact solver by Masashi Tamaki of Meiji University solving 199 of 200 instances using a modified brute-force approach, and a SAT-solver-based Java entry from Luebeck University also competing<sup>[10](https://pacechallenge.org/2016/09/12/results-PACE-2016/)</sup><sup> • </sup><sup>[13](https://pacechallenge.org/2016/treewidth/)</sup>.

## Applications

The central application is dynamic programming on tree decompositions. Many graph problems that are NP-hard in general become solvable in linear or polynomial time when the input graph has treewidth bounded by a constant, because a table can be computed over the bags, whose size is controlled by the width<sup>[2](https://www.stat.berkeley.edu/~mmahoney/pubs/im_treedecompositions.pdf)</sup><sup> • </sup><sup>[14](https://academic.oup.com/comjnl/article-abstract/51/3/255/407739)</sup>. Documented application areas include constraint satisfaction, computational biology, linear algebra, probabilistic networks, and machine learning<sup>[2](https://www.stat.berkeley.edu/~mmahoney/pubs/im_treedecompositions.pdf)</sup>. In probabilistic inference, tree decompositions are used in a preprocessing phase, and compilers exploit the fact that control flow graphs have small treewidth in practice to allocate registers via proper colorings<sup>[10](https://pacechallenge.org/2016/09/12/results-PACE-2016/)</sup>.

A practical constraint is memory. [Dynamic programming](https://www.edgepedia.org/dynamic-programming) over a decomposition stores tables at tree nodes, and Koster and colleagues reported instances they could not solve mainly because of memory limits; one line of work therefore optimizes the traversal of the decomposition tree to minimize the number of tables held simultaneously<sup>[15](https://doi.org/10.1016/j.disopt.2006.05.008)</sup>.

Treewidth-based methods also reach quantum simulation. A benchmarking study of tensor network contraction found that modern treewidth solvers from the PACE 2017 challenge were faster and had more consistent run times than domain-specific contraction algorithms on MERA datasets and QAOA circuits, moving the bottleneck away from finding a contraction order<sup>[16](https://pmc.ncbi.nlm.nih.gov/articles/PMC6298732/)</sup>.

## Related measures

Treewidth is one of several tree-likeness parameters. The treelength of a decomposition is the maximum diameter in \( G \) of its bags, and the treelength \( tl(G) \) is the minimum over all decompositions; trees have treewidth and treelength 1, but the two measures diverge elsewhere: a cycle has treewidth 2 and treelength \( \lceil n/3 \rceil \), while a clique has treewidth \( n-1 \) and treelength 1<sup>[17](https://doc.sagemath.org/html/en/reference/graphs/sage/graphs/graph_decompositions/tree_decomposition.html)</sup>. Pathwidth restricts the underlying tree to a path. For any graph, \( tl(G) \le \nu(G) \cdot (tw(G) + 1) \), where \( \nu(G) \) is the length of the longest geodesic cycle<sup>[2](https://www.stat.berkeley.edu/~mmahoney/pubs/im_treedecompositions.pdf)</sup>.

## References

1. [Neil Robertson and P. D. Seymour (1986). Graph minors. II. Algorithmic aspects of tree-width. Journal of Algorithms 7(3):309–322.](https://www.sciencedirect.com/science/article/pii/0196677486900234)
2. [Adcock, Sullivan, Mahoney et al. Tree decompositions and social graphs.](https://www.stat.berkeley.edu/~mmahoney/pubs/im_treedecompositions.pdf)
3. [Lecture 15, Treewidth, 6.854 Advanced Algorithms, MIT CSAIL.](https://courses.csail.mit.edu/6.854/18/Scribe/s25-online/s25-online.html)
4. [Tree Decomposition, ScienceDirect Topics overview.](https://www.sciencedirect.com/topics/computer-science/tree-decomposition)
5. [Molter, Zehavi, Zivan (2025). Treewidth Parameterized by Feedback Vertex Number. arXiv.](https://arxiv.org/abs/2504.18302)
6. [Bandwidth, expansion, treewidth, separators and universality for bounded-degree graphs. European Journal of Combinatorics.](https://doi.org/10.1016/j.ejc.2009.10.010)
7. [Graph minors. II. Algorithmic aspects of tree-width, excerpted definition.](https://vaclavblazej.github.io/parameters/html/i56ihO/)
8. [Chordal graphs and clique trees, Princeton lecture notes.](https://web.math.princeton.edu/~pds/papers/containers/paper.pdf)
9. [Neil Robertson and P. D. Seymour (1991). Graph minors. X. Obstructions to tree-decomposition. Journal of Combinatorial Theory B 52(2):153–190.](https://www.sciencedirect.com/science/article/pii/009589569190061N)
10. [Results of the First PACE Challenge (2016).](https://pacechallenge.org/2016/09/12/results-PACE-2016/)
11. [Belbasi, Fürer, Kumar (2024). Optimized 2-Approximation of Treewidth. arXiv.](https://arxiv.org/abs/2411.16918)
12. [Bodlaender, Koster (2008). Treewidth Computations I: Upper bounds.](https://www.researchgate.net/publication/266549721_Treewidth_computations_I_Upper_bounds)
13. [PACE 2016, Track A: Tree Width.](https://pacechallenge.org/2016/treewidth/)
14. [Bodlaender, Koster (2008). Combinatorial Optimization on Graphs of Bounded Treewidth. The Computer Journal 51(3):255–269.](https://academic.oup.com/comjnl/article-abstract/51/3/255/407739)
15. [Tree decompositions of graphs: Saving memory in dynamic programming. Discrete Optimization.](https://doi.org/10.1016/j.disopt.2006.05.008)
16. [Benchmarking treewidth as a practical component of tensor network simulations. PMC.](https://pmc.ncbi.nlm.nih.gov/articles/PMC6298732/)
17. [Tree decompositions, SageMath documentation.](https://doc.sagemath.org/html/en/reference/graphs/sage/graphs/graph_decompositions/tree_decomposition.html)

---
*Topic: Encyclopedia › Physical world and mathematics › Mathematics and statistics › Logic and discrete mathematics › General discrete mathematics and discrete structures › Graph theory › Graph theory subfields and named results › Structural and graph minor theory*

*Initially written Sep 17, 2026 · Reviewed: Sep 30, 2026; Oct 15, 2026 · Edited: Sep 30, 2026; Oct 15, 2026 · Last review: Oct 15, 2026*

*Copyright 2026 EdgeChat AI, a subsidiary of Biostate AI.*

License: Edgepedia Community License 1.0, https://www.edgepedia.org/edgepedia/license