# Treewidth

**Treewidth** is a graph parameter that measures how far a graph is from being a tree. It is defined as the minimum width of any tree decomposition of the graph, where a tree decomposition represents the graph's vertices as overlapping sets (bags) arranged on a tree, and the width is the size of the largest bag minus one<sup>[1](https://citeseerx.ist.psu.edu/document?doi=b67ee99675e342f05ed2fb0bdd2bd15b065d3354&repid=rep1&type=pdf)</sup>. The concept was introduced by [Neil Robertson](https://www.edgepedia.org/neil-robertson) and Paul Seymour in their Graph Minors project, and closely related notions were invented independently by several researchers in the 1980s, including partial k-trees (Arnborg and Proskurowski) and clique trees (Lauritzen and Spiegelhalter)<sup>[2](https://webdoc.sub.gwdg.de/ebook/serien/ah/UU-CS/2006-041.pdf)</sup>.

| Key fact | Detail |
|---|---|
| Definition | Minimum over all tree decompositions of max bag size minus one; denoted tw(G)<sup>[1](https://citeseerx.ist.psu.edu/document?doi=b67ee99675e342f05ed2fb0bdd2bd15b065d3354&repid=rep1&type=pdf)</sup> |
| Extremes | A tree has treewidth 1 (the smallest possible); a complete graph on n vertices has treewidth n − 1<sup>[3](https://doi.org/10.1016/j.jcta.2016.10.001)</sup><sup> • </sup><sup>[4](https://arxiv.org/abs/2211.07154)</sup> |
| Complexity | Deciding whether treewidth ≤ k is NP-complete; for fixed k it is fixed-parameter tractable<sup>[5](https://www.sciencedirect.com/topics/computer-science/tree-decomposition)</sup> |
| Exact algorithms | Bodlaender's 1996 linear-time algorithm for fixed k; Korhonen and Lokshtanov (2022) achieved 2^{O(k²)} n^{O(1)}<sup>[6](https://epubs.siam.org/doi/10.1137/S0097539793251219)</sup><sup> • </sup><sup>[4](https://arxiv.org/abs/2211.07154)</sup> |
| Algorithmic use | Dynamic programming over a decomposition runs in time exponential in the width, so bounded treewidth makes many NP-hard problems tractable<sup>[7](https://doi.org/10.1145/3731452)</sup> |
| Duality | tw(G) equals the maximum order of a bramble minus one (Seymour–Thomas theorem)<sup>[8](https://www.math.ens.psl.eu/~amini/Publications/Survey.pdf)</sup> |

## Definition

A tree decomposition of a graph G = (V, E) is a pair (T, X), where T is a tree and X = {B_i : i ∈ V(T)} is a collection of subsets of V called bags, satisfying three conditions<sup>[1](https://citeseerx.ist.psu.edu/document?doi=b67ee99675e342f05ed2fb0bdd2bd15b065d3354&repid=rep1&type=pdf)</sup>:

1. Every vertex of G belongs to at least one bag.
2. For every edge {u, v} of G, some bag contains both u and v.
3. For every vertex v, the bags containing v form a connected subtree of T.

The width of the decomposition is max |B_i| − 1, and the treewidth of G is the minimum width over all tree decompositions<sup>[1](https://citeseerx.ist.psu.edu/document?doi=b67ee99675e342f05ed2fb0bdd2bd15b065d3354&repid=rep1&type=pdf)</sup>. Informally, a graph has small treewidth if it can be constructed by piecing small graphs together in a tree structure<sup>[9](https://www.sciencedirect.com/science/article/pii/009589569190061N)</sup>.

The parameter behaves predictably on simple graphs. A graph has treewidth at most 1 if and only if every connected component is a tree, and the complete graph on n vertices has treewidth n − 1, the largest possible for a given vertex set<sup>[3](https://doi.org/10.1016/j.jcta.2016.10.001)</sup><sup> • </sup><sup>[4](https://arxiv.org/abs/2211.07154)</sup>. Treewidth is minor-monotone: if H is a minor of G, then tw(H) ≤ tw(G)<sup>[8](https://www.math.ens.psl.eu/~amini/Publications/Survey.pdf)</sup>.

## Alternative characterizations

Treewidth has several equivalent formulations that drive algorithm design. Given an elimination ordering of the vertices, the fill-in graph is built by connecting, for each vertex in turn, all pairs of its higher-numbered neighbors. A graph has treewidth at most k if and only if it has an elimination ordering in which each vertex has at most k higher-numbered neighbors in the fill-in graph, equivalently a triangulation (a chordal supergraph) with maximum clique size at most k + 1<sup>[2](https://webdoc.sub.gwdg.de/ebook/serien/ah/UU-CS/2006-041.pdf)</sup>. Chordal graphs, those in which every cycle of length at least four has a chord, are exactly the graphs that admit a tree decomposition in which every bag is a clique<sup>[2](https://webdoc.sub.gwdg.de/ebook/serien/ah/UU-CS/2006-041.pdf)</sup>.

There is also a min–max duality. A bramble is a collection of connected vertex sets in which any two sets in the collection touch (their union is connected); its order is the minimum number of vertices needed to hit every set. The Seymour–Thomas theorem states that tw(G) equals the maximum bramble order minus one<sup>[8](https://www.math.ens.psl.eu/~amini/Publications/Survey.pdf)</sup>. For an n × n grid, crosses through the grid form a bramble of order n, showing that grids have large treewidth and that treewidth is unbounded even on planar graphs<sup>[8](https://www.math.ens.psl.eu/~amini/Publications/Survey.pdf)</sup>.

## Computational complexity

Deciding whether a graph has treewidth at most k is NP-complete, a result due to Stefan Arnborg, Derek Corneil, and Andrzej Proskurowski<sup>[5](https://www.sciencedirect.com/topics/computer-science/tree-decomposition)</sup>. The problem is nevertheless fixed-parameter tractable: for fixed k it can be solved in time f(k) · n, where f depends only on k. Robertson and Seymour first established this using results from their Graph Minors project, though their argument was not constructive<sup>[5](https://www.sciencedirect.com/topics/computer-science/tree-decomposition)</sup>.

**Exact algorithms.** Hans L. Bodlaender, professor at [Utrecht University](https://www.edgepedia.org/utrecht-university), published in 1996 a linear-time algorithm that, for constant k, decides whether treewidth is at most k and, if so, constructs a tree decomposition of width at most k<sup>[6](https://epubs.siam.org/doi/10.1137/S0097539793251219)</sup>. The dependence on k in these algorithms stood at 2^{O(k³)} for three decades. In 2022, Tuukka Korhonen and Daniel Lokshtanov gave an algorithm running in time 2^{O(k²)} n^{O(1)} that outputs a decomposition of width at most k when one exists, resolving a long-standing open problem; it is also the first such algorithm not based on dynamic programming and running in polynomial space<sup>[4](https://arxiv.org/abs/2211.07154)</sup>.

**Approximation.** In 2023 Korhonen gave a single-exponential 2-approximation: in time 2^{O(k)} n the algorithm either outputs a decomposition of width at most 2k + 1 or determines that the treewidth exceeds k. This was the first 2-approximation faster than the known exact algorithms, improving on the previous best ratio of 5 in the same time bound<sup>[10](https://epubs.siam.org/doi/abs/10.1137/22M147551X)</sup>.

**Practical computation.** Because exact algorithms are slow in practice, experimental work relies on preprocessing, heuristics such as Minimum Degree and Minimum Fill-In that produce elimination orderings, and branch-and-bound methods that can compute treewidth exactly for graphs of roughly 30 to 60 vertices<sup>[2](https://webdoc.sub.gwdg.de/ebook/serien/ah/UU-CS/2006-041.pdf)</sup>. Lower bounds come from bramble-based techniques, which for planar graphs give bounds within a constant factor of the optimum<sup>[11](https://link.springer.com/article/10.1007/s00453-007-9056-z)</sup>.

## Algorithmic applications

The main use of treewidth is as a complexity barrier that, once low, makes hard problems easy. Many problems that are NP-hard on arbitrary graphs, including Hamiltonian Circuit, Independent Set, and Vertex Cover, become linear or polynomial time solvable on graphs of bounded treewidth<sup>[2](https://webdoc.sub.gwdg.de/ebook/serien/ah/UU-CS/2006-041.pdf)</sup>.

**Dynamic programming on decompositions.** The standard method computes a tree decomposition of small width, roots it, and fills tables bottom-up, one per bag; each table is computed from the bag's local information and its children's tables. The per-bag time is exponential in the bag size but independent of graph size, so the whole algorithm is linear when the width is constant<sup>[2](https://webdoc.sub.gwdg.de/ebook/serien/ah/UU-CS/2006-041.pdf)</sup>. The exponent matters: Dominating Set can be solved in time 3^{tw} · n^{O(1)} using dynamic programming and subset convolution, a bound reached only after repeated improvements<sup>[7](https://doi.org/10.1145/3731452)</sup>.

**Courcelle's theorem.** In a 1990 result, [Bruno Courcelle](https://www.edgepedia.org/bruno-courcelle) showed that any problem expressible in monadic second-order logic (MSO) admits a linear-time solution when the input graph has bounded treewidth.<sup>[12](https://www.sciencedirect.com/science/article/pii/S1571066109003533)</sup> The standard proof compiles the formula into a finite [tree automaton](https://www.edgepedia.org/tree-automaton) that runs over the tree decomposition<sup>[12](https://www.sciencedirect.com/science/article/pii/S1571066109003533)</sup>.

**Probabilistic networks and constraint satisfaction.** [Inference](https://www.edgepedia.org/inference) in probabilistic (Bayesian) networks is #P-hard in general, but the standard method moralizes the network's graph and applies the Lauritzen–Spiegelhalter algorithm, which runs in linear time when the moralized graph has small treewidth; this condition appears to hold for many real-world networks<sup>[2](https://webdoc.sub.gwdg.de/ebook/serien/ah/UU-CS/2006-041.pdf)</sup>. Tree decompositions likewise underlie tractable classes of constraint satisfaction problems, and hypertree width generalizes the idea to hypergraphs<sup>[13](https://www.researchgate.net/publication/220975376_Hypertree_Decompositions_A_Survey)</sup>.

**Electrical networks.** A biconnected electrical network can be reduced to a single edge between its terminals by series, parallel, and star-triangle rules if and only if it has treewidth at most three, a check that can be done in linear time<sup>[2](https://webdoc.sub.gwdg.de/ebook/serien/ah/UU-CS/2006-041.pdf)</sup>.

## The grid-minor theorem

A keystone of the Graph Minors project is the excluded grid theorem: there is a function f such that every graph of treewidth at least f(k) contains the k × k grid as a minor<sup>[14](https://www.mdpi.com/1999-4893/18/7/386)</sup>. Large grid minors are thus canonical obstructions to small treewidth<sup>[15](https://doi.org/10.1016/j.ejc.2021.103394)</sup>.

The quantitative gap between these quantities was long enormous. Robertson, Seymour, and Thomas showed that treewidth more than 20^{2r⁵} forces an r × r grid minor; successive work reduced this, and Chandra Chekuri and Julia Chuzhoy obtained the first polynomial bound. The current best upper bound is O(r⁹ polylog r), due to Chuzhoy and Tan, against a lower bound of Ω(r² log r)<sup>[16](https://www.sciencedirect.com/science/article/abs/pii/S0095895619300772)</sup>. For planar graphs a linear bound holds: every planar graph with no k × k grid minor has treewidth at most 6k − 5<sup>[17](https://www.researchgate.net/publication/24013953_Algorithmic_Meta-Theorems)</sup>.

## Related width parameters

Treewidth anchors a family of width measures. Requiring the decomposition tree to be a path gives path decomposition and pathwidth, so pathwidth is always at least treewidth<sup>[18](https://link.springer.com/article/10.1007/s00453-026-01404-5)</sup>. Treedepth, another invariant in the same family, admits a polynomial excluded-minor approximation in terms of grids, trees, and paths, analogous to the grid-minor theorem for treewidth<sup>[19](https://epubs.siam.org/doi/abs/10.1137/1.9781611975031.17)</sup>. Parameters tied to treewidth studied for their own algorithmic consequences include separation number, tangle number, and well-linked number<sup>[20](https://arxiv.org/abs/1312.3401)</sup>.

## References

1. [Definition of tree decomposition and treewidth, Fixed-Parameter Tractability (Citeseerx PDF)](https://citeseerx.ist.psu.edu/document?doi=b67ee99675e342f05ed2fb0bdd2bd15b065d3354&repid=rep1&type=pdf)
2. [Hans L. Bodlaender (2006). Treewidth: Characterizations, Applications, and Computations. Technical Report UU-CS-2006-101.](https://webdoc.sub.gwdg.de/ebook/serien/ah/UU-CS/2006-041.pdf)
3. [Courcelle's theorem for triangulations, Journal of Combinatorial Theory A (ScienceDirect)](https://doi.org/10.1016/j.jcta.2016.10.001)
4. [Tuukka Korhonen, Daniel Lokshtanov (2022). An Improved Parameterized Algorithm for Treewidth. arXiv:2211.07154.](https://arxiv.org/abs/2211.07154)
5. [Tree Decomposition overview, ScienceDirect Topics](https://www.sciencedirect.com/topics/computer-science/tree-decomposition)
6. [Hans L. Bodlaender (1996). A Linear-Time Algorithm for Finding Tree-Decompositions of Small Treewidth. SIAM J. Comput. 25(6): 1305–1317.](https://epubs.siam.org/doi/10.1137/S0097539793251219)
7. [Tight Complexity Bounds for Counting Generalized Dominating Sets in Bounded-Treewidth Graphs, ACM Transactions on Algorithms](https://doi.org/10.1145/3731452)
8. [Geometry of Graphs and Applications in Arithmetic and Dynamics (survey, ENS Paris)](https://www.math.ens.psl.eu/~amini/Publications/Survey.pdf)
9. [Neil Robertson, P.D. Seymour (1991). Graph minors. X. Obstructions to tree-decomposition. J. Combin. Theory Ser. B 52: 153–190.](https://www.sciencedirect.com/science/article/pii/009589569190061N)
10. [Tuukka Korhonen. A Single-Exponential Time 2-Approximation Algorithm for Treewidth. SIAM J. Comput.](https://epubs.siam.org/doi/abs/10.1137/22M147551X)
11. [Bodlaender, Grigoriev, Koster (2008). Treewidth Lower Bounds with Brambles. Algorithmica 51: 81–98.](https://link.springer.com/article/10.1007/s00453-007-9056-z)
12. [A Practical Approach to Courcelle's Theorem, ScienceDirect](https://www.sciencedirect.com/science/article/pii/S1571066109003533)
13. [Gottlob, Leone, Scarcello (2001). Hypertree Decompositions: A Survey. LNCS 2136.](https://www.researchgate.net/publication/220975376_Hypertree_Decompositions_A_Survey)
14. [The Behavior of Tree-Width and Path-Width Under Graph Operations and Graph Transformations, MDPI Algorithms](https://www.mdpi.com/1999-4893/18/7/386)
15. [On the tree-width of even-hole-free graphs, European Journal of Combinatorics](https://doi.org/10.1016/j.ejc.2021.103394)
16. [Linear min-max relation between the treewidth of an H-minor-free graph and its largest grid minor, J. Combin. Theory Ser. B](https://www.sciencedirect.com/science/article/abs/pii/S0095895619300772)
17. [Algorithmic Meta-Theorems (ResearchGate)](https://www.researchgate.net/publication/24013953_Algorithmic_Meta-Theorems)
18. [Graph and String Parameters: Connections Between Pathwidth, Cutwidth and the Locality Number, Algorithmica](https://link.springer.com/article/10.1007/s00453-026-01404-5)
19. [Kawarabayashi, Rossman. A Polynomial Excluded-Minor Approximation of Treedepth. SODA 2018, pp. 234–246.](https://epubs.siam.org/doi/abs/10.1137/1.9781611975031.17)
20. [Parameters Tied to Treewidth. arXiv:1312.3401.](https://arxiv.org/abs/1312.3401)

---
*Topic: Encyclopedia › Technology and the built world › Computing and digital systems › Artificial intelligence and data › Algorithms and computational methods › Graph and network algorithms › Algorithms on special graph classes*

*Initially written Sep 17, 2026 · Reviewed: Sep 30, 2026; Oct 15, 2026 · Edited: 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