Fact-checked by Grok 2 weeks ago

Treewidth

In graph theory, treewidth is a nonnegative integer parameter of an undirected graph that quantifies its structural complexity relative to trees, defined as the minimum width of any tree decomposition of the graph. A tree decomposition of a graph G = (V, E) is a pair (T, \{W_t \mid t \in V(T)\}), where T is a tree with node set V(T) and each W_t \subseteq V is a subset called a bag, such that: (1) \bigcup_{t \in V(T)} W_t = V; (2) for every edge uv \in E, there exists some t \in V(T) with u, v \in W_t; and (3) for every vertex v \in V, the set \{t \in V(T) \mid v \in W_t\} induces a connected subtree of T; the width of the decomposition is \max_{t \in V(T)} (|W_t| - 1), and the treewidth of G is the minimum such width over all tree decompositions.^[1]^[2] The concept was first introduced by Umberto Bertelè and Francesco Brioschi in 1972, further developed by Rudolf Halin in his 1976 study of S-functions on graphs, which captured separation properties equivalent to modern treewidth, though the explicit term and decomposition framework were introduced by Neil Robertson and Paul Seymour in their 1984 work on planar graphs and minors. Graphs of treewidth at most 1 are precisely the forests (acyclic graphs), treewidth 2 corresponds to series-parallel graphs, and complete graphs K_n have treewidth n-1. Bounded treewidth implies the absence of large grid minors, as established in the graph minors project, where Robertson and Seymour proved that excluding any fixed minor H bounds the treewidth by some function of |H|.^[1]^[3]^[4] Treewidth is central to parameterized complexity and algorithmic graph theory, enabling fixed-parameter tractable algorithms and dynamic programming techniques for NP-hard problems like independent set, dominating set, and graph coloring when the treewidth is treated as a parameter. For instance, many such problems solvable in time O(2^{O(k)} n) on n-vertex graphs of treewidth at most k. It also underpins approximation algorithms and structural results, such as the grid minor theorem, which states that high treewidth implies the presence of large grid minors. Computing or approximating treewidth is NP-hard, but practical heuristics and exact algorithms exist for moderate-sized graphs, with applications in database query optimization, VLSI design, and phylogenetic tree reconstruction.^[5]^[6]^[7]

Core Concepts

Definition

In graph theory, the treewidth of a graph G = (V, E) measures how closely G resembles a tree in its structure, providing a parameter that quantifies the complexity of solving optimization problems on G.^[8] This notion was introduced by Robertson and Seymour in their work on graph minors to characterize graphs with efficient algorithmic properties.^[1] A tree decomposition of G is a pair (T, \{X_i\}_{i \in I}), where T = (I, F) is a tree with node set I and edge set F, and each X_i \subseteq V is a subset called a bag. It must satisfy three properties: (1) every vertex v \in V belongs to at least one bag, i.e., \bigcup_{i \in I} X_i = V; (2) every edge uv \in E is contained in at least one bag, i.e., there exists i \in I such that \{u, v\} \subseteq X_i; and (3) for every vertex v \in V, the set of nodes \{i \in I \mid v \in X_i\} induces a connected subtree of T.^[8] The width of a tree decomposition is the size of the largest bag minus one, \max_{i \in I} (|X_i| - 1). The treewidth of G, denoted \mathrm{tw}(G), is the minimum width over all possible tree decompositions of G:

\mathrm{tw}(G) = \min_{(T, \{X_i\}_{i \in I})} \max_{i \in I} (|X_i| - 1).

This subtraction of one ensures that trees have treewidth 1, aligning with their simple structure where bags need only cover edges without larger overlaps.^[8] More precisely, the treewidth relates to chordal graphs, where \mathrm{tw}(G) equals the size of the largest clique minus one in a minimum chordal completion of G, as chordal graphs admit tree decompositions in which each bag induces a clique.^[8] Treewidth generalizes the tree structure to broader graph classes, enabling dynamic programming algorithms that run in time exponential only in the treewidth, thus efficiently solving NP-hard problems on graphs with bounded treewidth.^[8]

Tree Decompositions

A tree decomposition of a graph G = (V, E) consists of a tree T = (I, F) and a collection of subsets X_i \subseteq V for each node i \in I, called bags, such that: (1) \bigcup_{i \in I} X_i = V; (2) for every edge \{u, v\} \in E, there exists some i \in I with \{u, v\} \subseteq X_i; and (3) for every vertex v \in V, the set of nodes \{i \in I \mid v \in X_i\} induces a connected subtree of T. This running intersection property in condition (3) ensures that the decomposition captures the connectivity of G in a tree-like manner.^[9]^[10] To construct a tree decomposition, one can start with an arbitrary tree T and assign bags X_i iteratively, ensuring the three properties hold; for instance, heuristics like minimum degree elimination build it by selecting a vertex of minimum degree, forming a bag with its neighbors, adding edges to make them a clique if needed, and recursing on the remaining graph, then attaching the new bag to the decomposition of the subgraph. This process preserves the tree structure while covering all vertices and edges. The adhesion set between two adjacent nodes i and j in T is defined as X_i \cap X_j, which acts as a separator in G, disconnecting the subgraphs induced by the components on either side of the edge \{i, j\} in T. These adhesion sets facilitate the modular analysis of G across the decomposition.^[10] A variation useful for algorithms is the nice tree decomposition, which is a rooted tree decomposition where each node is one of four types: a leaf node with an empty bag; an introduce node, whose bag adds exactly one vertex to its child's bag; a forget node, whose bag removes exactly one vertex from its child's bag; or a join node, with two children having identical bags. Any tree decomposition of width at most k can be transformed into a nice one of width at most k with O(n) nodes in linear time, where n = |V|, enabling efficient dynamic programming by standardizing bag changes.^[11] Treewidth is equivalently defined via chordal completions: a graph G has treewidth at most k if and only if there exists a chordal supergraph H of G (obtained by adding edges to G) with maximum clique size \omega(H) \leq k+1, and the treewidth is the minimum such k. In this view, the bags of an optimal tree decomposition correspond to the maximal cliques of this minimal chordal completion, with the tree T encoding the clique intersection graph, which is itself a tree for chordal graphs.^[10] The equivalence between tree decompositions and partial k-trees—graphs built by starting with a clique of size at most k+1 and repeatedly adding a vertex adjacent to at most k existing vertices—can be sketched as follows. First, a partial k-tree admits a tree decomposition of width at most k: for each added vertex v with neighbors forming a clique C of size at most k, introduce a new bag X = C \cup \{v\} attached to a bag containing C in the decomposition of the prior graph, preserving the running intersection property since C connects the subtrees. Conversely, given a tree decomposition of width at most k, root T at an arbitrary node and order vertices by a post-order traversal (processing leaves first); for each vertex v first appearing in bag X_i, its earlier neighbors in the order lie in the subtree below i, and by the running intersection, they form a clique of size at most k in the bags along paths, yielding a valid partial k-tree construction in reverse. This bidirectional construction establishes the equivalence.^[10]

Basic Properties

Treewidth exhibits monotonicity under the subgraph relation: if G is a subgraph of H, then \mathrm{tw}(G) \leq \mathrm{tw}(H). This property arises because any tree decomposition of H induces a valid tree decomposition of G by restricting the bags to vertices in G.^[12] Graphs of treewidth at most k are known as partial k-trees, which are precisely the subgraphs of k-trees; here, k-trees are the maximal graphs (under edge addition) with treewidth exactly k, constructed by starting with a clique of size k+1 and repeatedly adding vertices adjacent to exactly k existing vertices.^[13] A fundamental lower bound relates treewidth to the clique number: for any graph G, \mathrm{tw}(G) \geq \omega(G) - 1, where \omega(G) denotes the size of the largest clique in G. This follows from the fact that the complete graph K_m has treewidth m-1, and treewidth is subgraph-monotone.^[12] Treewidth admits a duality characterization via brambles. A bramble in a graph G is a nonempty collection of connected subgraphs of G such that any two sets in the collection share a common vertex, and the order of the bramble is the size of the smallest vertex set that intersects every member of the collection. The bramble number \mathrm{bn}(G) is the maximum order over all brambles in G. Seymour and Thomas proved that \mathrm{tw}(G) = \mathrm{bn}(G) - 1 for every finite graph G. In fact, this equality can be refined as \mathrm{tw}(G) = \max(\omega(G) - 1, \mathrm{bn}(G) - 1), since the clique bound is subsumed by the bramble characterization. Havens provide a dual perspective to brambles for characterizing treewidth. A haven of order k in G is a function assigning to certain subtrees of a binary search tree of height k a nonempty subset of vertices of G that satisfies specific consistency and escape conditions in a pursuit-evasion game interpretation. The haven number \mathrm{hn}(G) is the maximum order of a haven in G, and Seymour and Thomas established that \mathrm{hn}(G) = \mathrm{tw}(G) + 1. This haven-based duality complements the bramble formulation, as havens model defensive strategies against separators, mirroring how brambles represent interconnected structures resistant to hitting sets.^[12] Regarding extremal aspects, there is no known closed-form formula for the extremal function f(n,k), the maximum number of edges in an n-vertex graph of treewidth at most k. However, k-trees achieve \binom{k+1}{2} + k(n - k - 1) edges, providing an upper bound on density.^[14] For random graphs, the expected treewidth of the Erdős–Rényi model G(n,p) with constant p > 0 grows linearly as \Theta(n), reflecting the dense, highly connected nature that precludes low treewidth. In sparser regimes, such as p = c/n with c > 1 (supercritical case), the treewidth is \Theta(n / (c - 1)) with high probability, still linear in n but with coefficient depending on c.^[15]

Examples and Characterizations

Illustrative Examples

Trees provide one of the simplest examples of graphs with bounded treewidth. Any tree has treewidth exactly 1. A tree decomposition can be constructed as a path where each bag consists of two adjacent vertices connected by an edge in the tree, ensuring that every edge is covered by some bag and the intersection properties hold. This reflects the acyclic, tree-like structure of the graph itself.^[16] Cycles illustrate a slight departure from tree-like behavior. A cycle graph C_n for n \geq 3 has treewidth exactly 2. One possible tree decomposition uses a path of bags, each of size 3, where consecutive bags overlap on two vertices to cover the cycle's edges sequentially; for instance, bags might contain vertices \{v_i, v_{i+1}, v_{i+2}\} shifting around the cycle. This requires bags larger than in trees to account for the single cycle.^[16] Complete graphs K_n represent the opposite extreme, with high treewidth. The complete graph on n vertices has treewidth exactly n-1. The optimal decomposition consists of a single bag containing all n vertices, as every pair must intersect in every bag to cover all edges, maximizing the bag size. This underscores how cliques force large overlaps in any decomposition.^[16]^[17] Series-parallel graphs, built recursively from edges via series and parallel compositions, have treewidth at most 2. Their decompositions mirror the recursive structure: starting from an edge (treewidth 1), series composition joins decompositions at a vertex, and parallel adds edges covered by existing bags of size at most 3. This keeps the width bounded despite multiple paths between terminals.^[16] Grid graphs offer insight into planar structures with growing treewidth. An m \times n grid graph has treewidth exactly \min(m, n). For a square n \times n grid, the treewidth is n, achievable by a decomposition where bags correspond to rows or columns, with overlaps ensuring edge coverage; larger dimensions require proportionally larger bags to separate the grid's interconnected layers.^[17] Outerplanar graphs, which admit a planar embedding with all vertices on the outer face, also have treewidth at most 2. A tree decomposition can be derived from a Hamiltonian path on the outer face, augmented with adjacent inner chords in bags of size at most 3, capturing the graph's near-tree topology without deep nesting.^[16]

Graph Families with Bounded Treewidth

Partial k-trees are precisely the graphs with treewidth at most k. These graphs are constructed recursively: begin with the complete graph K_{k+1}, which has treewidth exactly k, and repeatedly add a new vertex adjacent to at most k vertices already in the graph.^[18] This construction ensures that partial k-trees capture all graphs admitting a tree decomposition of width at most k, providing a constructive characterization of bounded treewidth classes.^[19] Series-parallel graphs form an important subclass with treewidth at most 2. They are defined recursively starting from a single edge and built through series compositions (identifying an endpoint of one graph with a source or sink of another) and parallel compositions (identifying sources and sinks of two graphs).^[20] This two-terminal recursive structure allows for efficient tree decompositions of width 2, highlighting their tree-like connectivity despite containing cycles.^[21] Outerplanar graphs, a proper subclass of planar graphs, also have treewidth at most 2. These graphs admit a planar embedding where all vertices lie on the outer face, limiting their structural complexity and ensuring bounded treewidth through decompositions based on facial triangles.^[22] More generally, k-outerplanar graphs—iterated subclasses of outerplanar graphs obtained by removing the outer face k times—have treewidth at most 3k - 1, demonstrating how increasing embedding restrictions in planar families yield linear bounds on treewidth.^[23] Interval graphs, which model intersections of intervals on a line, are chordal graphs, and chordal graphs have treewidth exactly equal to the size of their largest clique minus one. Consequently, interval graphs with bounded maximum clique size possess bounded treewidth.^[24] This property extends to other intersection graphs that are chordal with bounded clique number, such as certain comparability graphs, where the treewidth is directly controlled by the intersection multiplicity.^[25]

Forbidden Minors and Structural Theorems

The class of graphs with treewidth at most k is minor-closed, meaning that if a graph G has treewidth exceeding k, then G contains as a minor some graph from a finite forbidden set M_k whose members have treewidth greater than k.^[26] This characterization follows from the Robertson–Seymour theorem, which establishes that every minor-closed family of graphs is defined by a finite list of excluded minors. The theorem's proof spans a series of 23 papers, with the finiteness result culminating in the demonstration that the minor relation on graphs forms a well-quasi-order. For small values of k, explicit forbidden minors are known. Graphs of treewidth at most 1 exclude K_3 as a minor, corresponding precisely to forests.^[26] For treewidth at most 2, the forbidden minor is K_4, characterizing series-parallel graphs.^[26] While K_4 suffices for treewidth 2, higher values introduce additional obstructions; for instance, graphs of treewidth at most 3 exclude four minimal minors: K_5, the octahedron K_{2,2,2}, the Wagner graph, and the pentagonal prism C_5 \times K_2.^[27] Bramble-haven duality provides a structural link between treewidth and minor obstructions, framing treewidth in terms of maximal "entangled" substructures resistant to separation. A bramble is a collection of connected subgraphs where every pair intersects or is joined by an edge, and its order is the minimum size of a hitting set; havens are ultrafilters on separations that avoid small cuts. The duality theorem states that the treewidth of a graph equals the maximum order of a bramble minus one, equivalently bounding the order of maximal havens. In minor terms, this duality underpins the Robertson–Seymour framework by showing that high treewidth implies unavoidable minor configurations, such as brambles that force grid-like minors. The grid theorem exemplifies these obstructions quantitatively: every graph containing an r \times r grid as a minor has treewidth at least r, and conversely, graphs with sufficiently large treewidth contain a large grid minor. Specifically, every graph of treewidth at least f(r) contains an r \times r grid minor for some polynomial f(r); early bounds by Robertson and Seymour were exponential, but recent refinements yield polynomial dependence, with the best known upper bound O(r^9 \mathrm{polylog}\, r) as of 2020.^[28] This theorem highlights grids as prototypical high-treewidth minors, essential for excluding bounded treewidth classes.^[1] No explicit complete list of M_k exists for general k > 3, as the number of minimal forbidden minors grows rapidly—reaching 75 for treewidth at most 4—and enumerating them is computationally intensive, often requiring exponential time due to the underlying minor-testing complexity. These challenges underscore the theoretical power of the Robertson–Seymour characterization while limiting practical applications beyond small k.

Algorithms and Computation

Computing Treewidth

Computing the treewidth of a graph is a fundamental problem in graph algorithms, known to be NP-complete (Arnborg, Corneil, and Proskurowski, 1987), even when k is part of the input and small, such as deciding if the treewidth is at most 3 for graphs in certain classes like co-bipartite graphs.^[29] This hardness result, established by Arnborg, Corneil, and Proskurowski in 1987, holds for general graphs and underscores the computational challenges involved. Despite this, the problem is fixed-parameter tractable when parameterized by the treewidth k itself, meaning there exist algorithms whose running time is f(k) \cdot n^{O(1)} for some function f depending only on k and input size n.^[11] Exact algorithms for computing treewidth leverage this FPT property. A seminal linear-time algorithm for fixed k, due to Bodlaender in 1993, determines whether the treewidth is at most k and constructs a corresponding tree decomposition in O(2^{O(k^3)} n) time if it exists.^[11] This approach uses dynamic programming on a reduced graph after preprocessing steps like edge contractions and simplicial vertex removals. More recently, Korhonen and Lokshtanov improved the dependency on k in 2023, achieving $2^{O(k^2)} n^4 time while maintaining the exactness and output of an optimal tree decomposition.^[30] These FPT algorithms are practical for small k but become infeasible as k grows due to the exponential terms. Approximation algorithms provide efficient alternatives when exact computation is impractical. Korhonen's 2021 algorithm delivers a 2-approximation—producing a tree decomposition of width at most $2k if the true treewidth is k—in $2^{O(k)} n time, marking the first such method faster than exact solvers for moderate k. Independently, Belbasi and Fürer in 2021 refined Reed's earlier framework to achieve a (1+\epsilon)k-approximation for any \epsilon > 0, with running time n^{O(\log k / \epsilon)} that scales better for larger graphs despite higher polynomial dependence. In 2024, Bonsma et al. further optimized the 2-approximation, achieving linear FPT time with a significantly reduced constant in the exponent.^[31] These advancements balance approximation quality with efficiency, enabling applications on larger instances. For practical computation on real-world graphs, where exact or tight approximations may be too costly, heuristics offer fast upper bounds on treewidth via elimination orders. The minimum degree elimination heuristic iteratively selects and eliminates a vertex of minimum degree, adding edges to connect its neighbors, yielding a chordal supergraph whose clique number upper-bounds the treewidth; this approach is simple and often effective for sparse graphs.^[32] Chordal graph approaches, such as minimum fill-in heuristics, extend this by prioritizing eliminations that minimize added edges (fill-ins), producing triangulations closer to optimal and thus tighter treewidth estimates, though at higher preprocessing cost.^[32] These methods, while not guaranteed to find the exact value, integrate well with dynamic programming frameworks for subsequent graph problems.

Dynamic Programming on Tree Decompositions

Dynamic programming on tree decompositions provides a powerful framework for solving NP-hard graph problems efficiently when the input graph has bounded treewidth. By exploiting the tree-like structure of the decomposition, algorithms can compute solutions for subgraphs induced by the bags and combine them bottom-up along the tree, avoiding the exponential explosion typical of brute-force approaches on general graphs. This technique transforms problems that are intractable in general into fixed-parameter tractable (FPT) ones when parameterized by treewidth. The general approach relies on a nice tree decomposition, which refines an arbitrary tree decomposition into a binary tree with four node types: leaf nodes (empty bags), introduce nodes (adding one vertex to the parent bag), forget nodes (removing one vertex from the parent bag), and join nodes (merging two child subtrees with identical bags). For a problem, dynamic programming tables are associated with each node, storing relevant partial solutions for the subgraph consisting of all vertices forgotten below that node plus the current bag. For an introduce node adding vertex v, the table extends the parent's by considering choices for v (e.g., inclusion or exclusion in a cover). Forget nodes project out the forgotten vertex by taking minima or maxima over its states. Join nodes combine child tables via products or convolutions, ensuring compatibility on the shared bag. Leaf nodes initialize with base cases. Processing the tree bottom-up yields the global solution at the root. This process runs in time O(2^{O(\mathrm{tw})} n) for many problems, where \mathrm{tw} is the treewidth and n the number of vertices, as table sizes are exponential in bag size (at most \mathrm{tw}+1) and the decomposition has O(n) nodes. Specific problems illustrate the framework's effectiveness. For the vertex cover problem, the table at each node i with bag X_i stores, for each subset S \subseteq X_i, the minimum size of a vertex cover for the processed subgraph using exactly S from the bag. Transitions ensure edges incident to forgotten vertices are covered, yielding an exact solution in O(2^{\mathrm{tw}} n) time. Similarly, the maximum independent set uses tables tracking subsets of the bag that form independent sets in the subgraph, with joins verifying no edges between child solutions, also in O(2^{\mathrm{tw}} n) time. The dominating set problem extends this by tracking subsets that dominate the subgraph and bag, with a standard implementation in O(3^{\mathrm{tw}} n) time, though optimized variants achieve O((2 + \epsilon)^{\mathrm{tw}} n) for any \epsilon > 0. These algorithms assume a tree decomposition is given; computing one adds a preprocessing factor but preserves FPT status. Problems expressible in monadic second-order (MSO) logic, such as the above, admit uniform dynamic programming schemes translating the logical formula into table states over bag subsets or colorings, resulting in FPT algorithms with runtime f(\mathrm{tw}) n where f depends on the formula. Recent advancements refine constants for specific cases; for instance, graph coloring can be solved in O(2.5^{\mathrm{tw}} n^{O(1)}) time using refined state encodings that exploit symmetry in color assignments. These improvements highlight ongoing efforts to tighten exponential dependencies while maintaining broad applicability.^[33]

Courcelle's Theorem

Courcelle's theorem, a seminal result in graph theory and parameterized complexity, asserts that for any fixed integer k and any property of graphs expressible in monadic second-order logic (MSO), there exists an algorithm that decides whether a given n-vertex graph G with treewidth at most k satisfies the property in time O(f(k) \cdot n), where f is a computable function depending only on the formula and k. This logic extends first-order logic by allowing quantification over unary predicates, i.e., sets of vertices or edges. Specifically, MSO_1 permits quantification solely over subsets of vertices, while MSO_2 additionally allows quantification over subsets of edges; on classes of graphs with bounded treewidth, MSO_1 and MSO_2 possess equivalent expressive power, as the edges can be decomposed into a bounded number of matchings expressible in MSO_1.^[34]^[35] The proof relies on translating the MSO formula into an equivalent finite automaton that operates on a tree decomposition of the graph. Given a tree decomposition of width at most k, the automaton processes the bags (subsets of at most k+1 vertices) bottom-up along the tree structure, maintaining a finite state that tracks the satisfaction of quantified set constraints relative to the partial graph built so far. Recognition occurs if the root bag accepts the initial state, ensuring the entire property holds; this bottom-up evaluation yields the linear-time complexity in n, with the state space exploding as a tower of exponentials in k and the formula size.^[34]^[36] This theorem has profound implications for algorithm design on bounded-treewidth graphs, enabling linear-time solutions (up to the f(k) factor) for a wide class of NP-hard problems expressible in MSO_2, such as deciding Hamiltonicity—via quantification over a vertex set inducing a cycle covering all vertices—or the Steiner tree problem, where an optimal connecting subgraph for a terminal set can be found using an extension to optimization via local search on the decomposition. As a universal meta-theorem, it subsumes dynamic programming techniques for specific problems, providing a logical foundation for their fixed-parameter tractability.^[34]^[37]^[36] Despite its theoretical power, the theorem's practicality is limited by the enormous growth of f(k), often involving iterated exponentials that render it unusable even for small k (e.g., k=3) due to astronomical constants. Recent efforts have focused on derandomized and more efficient implementations, such as specialized automata constructions and approximations that reduce overhead for common problems, though full linear-time MSO model-checking remains challenging in practice.^[36]^[38]

Pathwidth

Pathwidth is a linear variant of treewidth, obtained by restricting the underlying tree in a tree decomposition to be a path. Formally, a path decomposition of a graph G = (V, E) is a sequence of subsets X_1, X_2, \dots, X_m \subseteq V (the bags) satisfying three conditions: (1) \bigcup_{i=1}^m X_i = V; (2) for every edge uv \in E, there exists some i such that u, v \in X_i; and (3) for every vertex v \in V, the indices i for which v \in X_i form a consecutive interval [l_v, r_v]. The width of this decomposition is \max_{1 \leq i \leq m} (|X_i| - 1), and the pathwidth \mathrm{pw}(G) is the minimum width over all path decompositions of G. This parameter was introduced as a tool in the study of graph minors. Since every path is a tree, any path decomposition is also a tree decomposition, implying \mathrm{pw}(G) \geq \mathrm{tw}(G) for every graph G. Equality holds for certain structured graphs, such as caterpillars—trees where all vertices lie within distance 1 of a central path—which have both treewidth and pathwidth equal to 1, as they admit a path decomposition where each bag consists of the central path vertices plus at most one leaf. For interval graphs, pathwidth also equals treewidth, both given by \omega(G) - 1, where \omega(G) is the size of the maximum clique; this follows from the linear ordering of maximal cliques in the interval representation, which yields an optimal path decomposition.^[39] Determining the pathwidth of a general graph is NP-complete. Fixed-parameter tractable algorithms exist, however, with running time $2^{O(\mathrm{pw}^2)} n^{O(1)} for a graph on n vertices, leveraging dynamic programming along the path structure. These algorithms are more demanding than those for treewidth due to the linearity constraint, which limits decomposition flexibility.^[40] Pathwidth finds applications in approximating the bandwidth of a graph, defined as the minimum, over all bijections \phi: V \to \{1, \dots, n\}, of \max_{uv \in E} |\phi(u) - \phi(v)|. Notably, \mathrm{pw}(G) \leq \mathrm{bw}(G) holds for every graph G, and pathwidth provides structural insights for developing approximation algorithms for bandwidth, particularly in completion problems to proper interval graphs.^[41]^[42]

Branchwidth

Branchwidth is a graph parameter closely related to treewidth, defined via branch decompositions that provide a binary tree-based clustering of the graph's edges. A branch decomposition of an undirected graph G is a pair (T, \tau), where T is an unrooted binary tree whose leaves are in one-to-one correspondence with the edges of G via the bijection \tau, and every internal vertex of T has degree three. For each edge e of T, removing e partitions the leaves into two sets L_e and R_e, inducing a bipartition of the edges of G. The order of e is the size of the cutset, defined as the number of vertices in G that are incident to at least one edge in L_e and at least one edge in R_e. The width of the branch decomposition is the maximum order over all edges of T, and the branchwidth of G, denoted bw(G), is the minimum width over all possible branch decompositions of G.^[9]^[43] Branchwidth and treewidth are linearly equivalent measures of graph connectivity. Specifically, for any graph G, bw(G) \leq tw(G) + 1 and tw(G) + 1 \leq \frac{3}{2} bw(G), implying that the two parameters differ by at most 1 for connected graphs G \neq K_2.^[9]^[44] This equivalence allows branchwidth to serve as an alternative framework for analyzing the same structural properties as treewidth, often with advantages in certain decompositional contexts. Computing the branchwidth of a graph is NP-hard, mirroring the computational hardness of treewidth. However, fixed-parameter tractable algorithms exist, such as an O^*(2^{|E|})-time algorithm for exact computation and more efficient approximations. Branchwidth generalizes naturally to matroid theory via the connectivity function of a matroid M on ground set E, where \eta_M(X) = r(X) + r(E \setminus X) - r(M) + 1 for X \subseteq E, and the branchwidth is defined analogously using this function; for graphic matroids, the branchwidth equals that of the underlying graph when the graph is 2-edge-connected.^[45]^[44]^[46] In duality with obstruction sets, branchwidth relates to tangles, which are maximal consistent families of high-order separations that certify large branchwidth: a graph has branchwidth at most k if and only if it has no tangle of order k+1. This contrasts with brambles, which play a similar certifying role for treewidth.^[44] Branchwidth facilitates approximation algorithms in scenarios where binary decompositions simplify analysis, such as a polynomial-time constant-factor approximation for the branchwidth of symmetric submodular functions, with applications to approximating clique-width and rank-width. It also enables fixed-parameter tractable 2-approximations for connectivity functions, improving efficiency in parameterized problems on graphs and matroids.^[47]^[48]

Local Treewidth and Diameter

The local treewidth of a graph G at radius r, denoted \text{ltw}(G, r), is defined as the maximum treewidth over all induced subgraphs consisting of the closed r-neighborhoods of vertices in G:

\text{ltw}(G, r) = \max_{v \in V(G)} \text{tw}\bigl(G[N_r^G]\bigr),

where N_r^G is the set of vertices in G at distance at most r from v, including v itself.^[49] A graph class has bounded local treewidth if there exists a function f such that \text{ltw}(G, r) \leq f(r) for every graph G in the class and every r \geq 0.^[50] Graphs with bounded local treewidth exhibit structural properties similar to those of bounded treewidth graphs, notably the existence of small separators. Specifically, every induced subgraph of treewidth at most k admits a separator of size at most k+1 that balances the component sizes, and this extends locally to imply the presence of sublinear-sized separators in graphs where local treewidth is controlled by a slowly growing function f(r).^[51] The diameter of a graph provides a bridge between local and global treewidth measures. Graphs with small diameter can exhibit arbitrarily large treewidth, as complete graphs have diameter 1 and treewidth n-1 for n vertices.^[52] However, in graph classes with bounded local treewidth, the global treewidth is controlled by the diameter D: there exists a function f such that \text{tw}(G) \leq f(D) for any graph G in the class.^[53] More precisely, since local treewidth is non-decreasing in r and the entire graph is contained in some D-neighborhood, \text{tw}(G) \leq \text{ltw}(G, D) \leq f(D). In minor-closed classes, this holds if and only if the class excludes some apex minor.^[53] For a graph of diameter D where \text{ltw}(G, r) \leq k for r = D/2, the global treewidth is then bounded by some function f(k, D), as the radius satisfies D/2 \leq \rho \leq D and the structure allows chaining local decompositions across the diameter.^[49] Classes of sparse graphs with bounded expansion provide key applications of bounded local treewidth. Such classes, characterized by controlled growth in the density of shallow minors, satisfy \text{ltw}(G, r) = O(r^c) for some constant c (typically c=1 or $2), enabling efficient algorithms for problems intractable on general graphs, such as first-order logic model checking in linear time.^[54] This property underpins meta-theorems for parameterized algorithms on these graphs, generalizing results from bounded treewidth to sparser settings without global width restrictions.^[55]

Other Parameters

The presence of an r \times r grid as a minor in a graph G implies that the treewidth of G is at least r, since the treewidth of the r \times r grid graph itself is exactly r.^[56] This provides a direct lower bound on treewidth from the size of the largest grid minor. The converse relationship is partially understood through the excluded grid theorem, which states that graphs excluding an r \times r grid as a minor have treewidth bounded by a function f(r); while the original bound by Robertson and Seymour was super-exponential, recent results establish a polynomial bound f(r) = O(r^9 \cdot \mathrm{polylog}(r)).^[57] The Hadwiger number \eta(G) of a graph G is the largest integer h such that G contains a complete graph K_h as a minor, representing the size of the largest clique minor. This parameter relates to treewidth through structural graph theory, particularly via the S-functions in the Robertson-Seymour graph minors project, which describe obstructions to bounded treewidth and connect clique minors to overall graph structure. Recent work characterizes hereditary graph classes where large treewidth forces a large Hadwiger number, revealing a dichotomy: either high treewidth implies \eta(G) \geq \Omega(\mathrm{tw}(G)), or the class excludes certain induced subgraphs that bound the Hadwiger number independently of treewidth.^[58] Tree-depth, denoted \mathrm{td}(G), measures the minimum height of a rooted elimination tree for G, where edges connect ancestors and descendants in the tree. A known lower bound relates tree-depth to treewidth and graph size: \mathrm{td}(G) \geq \log_2 (n / 2^{\mathrm{tw}(G)}), reflecting how bounded treewidth limits the branching in elimination schemes relative to the vertex count n. This bound highlights that while tree-depth can exceed treewidth (e.g., paths have treewidth 1 but tree-depth \Theta(\log n)), their interplay constrains structural complexity in sparse graphs.^[59] Clique-width, denoted \mathrm{cw}(G), is the minimum number of labels needed to construct G using specific graph operations, often smaller than treewidth but useful for algorithmic tractability. Graphs of treewidth k satisfy \mathrm{cw}(G) \leq 2^{O(k \log k)}, derived from converting tree decompositions into clique-width expressions via label management across bags; however, this bound is not tight, as some graphs (e.g., certain bipartite graphs) have clique-width much smaller than exponential in treewidth.^[60] In the 2020s, research on treewidth versus tree-depth has advanced approximation algorithms and hardness results, including improved excluded-minor approximations for tree-depth (showing O(\mathrm{tw} \cdot \log n / \log \log n) upper bounds in minor-closed classes) and inapproximability thresholds under the ETH, where distinguishing tree-depth O(\log n) from \omega(\log n / \log \log n) requires exponential time.^[61] These developments underscore tighter quantitative links, such as \mathrm{td}(G) = O(\mathrm{tw}(G) \log^2 n) for planar graphs, enhancing dynamic programming applications.^[62]

References

[1]
Graph minors. III. Planar tree-width - ScienceDirect.com
The “tree-width” of a graph is defined and it is proved that for any fixed planar graph H, every planar graph with sufficiently large tree-width has a minor ...
[2]
[PDF] Tree-width and planar minors - Math (Princeton)
A graph has tree-width w if w is the minimum such that it admits a tree-decomposition satisfying |Wt| ≤ w + 1 for each t ∈ V (T). A graph G has an H-minor if a ...
[3]
Treewidth? - American Mathematical Society
In 23 papers published from 1983 to 2012, Robert- son and Seymour found that the graphs in any minor- closed class have tree-decompositions in which each bag.Missing: original | Show results with:original
[4]
[PDF] Treewidth, Applications, and some Recent Developments
Applications of Treewidth. • Graph Theory. • Polynomial-time algorithms for problems on graphs/ structures with bounded/fixed treewidth. • Fixed parameter ...
[5]
Large-treewidth graph decompositions and applications
Treewidth is a graph parameter that plays a fundamental role in several structural and algorithmic results. We study the problem of decomposing a given ...
[6]
[PDF] Known Algorithms on Graphs of Bounded Treewidth are Probably ...
Jan 14, 2018 · Algorithms for graph problems on bounded treewidth graphs have found many uses as subroutines in approx- imation algorithms [7, 24, 25, 36], ...
[7]
https://sites.cs.ucsb.edu/~daniello/papers/knownOptimalTALG18.pdf
[8]
[PDF] Graph Minors. X. Obstructions to Tree- Decomposition
ROBERTSON AND SEYMOUR. 5. BRANCH-WIDTH AND TREE-WIDTH. A tree-decomposition of a hypergraph G is a pair (T, z), where T is a tree and for t E V(T), z(t) is a ...
[9]
[PDF] Treewidth: Characterizations, Applications, and Computations
This paper gives a short survey on algorithmic aspects of the treewidth of graphs. ... Bodlaender. New upper bound heuristics for treewidth. In S. E. ...
[10]
A Linear-Time Algorithm for Finding Tree-Decompositions of Small ...
The Pathwidth and Treewidth of Cographs · Hans L. Bodlaender; ,; Rolf H. Möhring. Abstract. It is shown that the pathwidth of a cograph equals its treewidth, ...
[11]
[PDF] Graph Minors
Our goal in this last chapter is a single theorem, one which dwarfs any other result in graph theory and may doubtless be counted among the.
[12]
[PDF] A partial k-arboretum of graphs with bounded treewidth
Treewidth is a powerful concept for graph studies. A graph with treewidth at most k is a partial k-tree, and a subgraph of a chordal graph with max clique size ...Missing: monotonicity | Show results with:monotonicity
[13]
Treewidth of Erdős–Rényi random graphs, random intersection ...
We study conditions under which the treewidth of three different classes of random graphs is linear in the number of vertices. For the Erdős–Rényi random ...
[14]
https://mathworld.wolfram.com/k-Tree.html
[15]
[PDF] The Impact of Treewidth on ASP Grounding and Solving - IJCAI
Trees have treewidth 1. Grids of size n, the complete graph Kn with n nodes, and the complete bipartite graph Kn,n all have treewidth n.
[16]
[PDF] Treewidth I
Treewidth is the least integer k such that a graph is a partial k-tree, or the most general search for a tree structure inside a graph.
[17]
[PDF] Treewidth: Algorithmic techniques and results
amongst others, graphs of treewidth at most k are also known as partial k-trees. A notion related to treewidth is pathwidth, de ned rst in [99]. A tree ...
[18]
[PDF] Lecture 5: November 4 5.1 Recap of tree-width 5.2 Properties of tree ...
We will prove in this subsection that any series-parallel graph has tree-width atmost 2. First, we give an equivalent definition of series-parallel graphs that ...
[19]
A polynomial time algorithm to compute the connected treewidth of a ...
May 15, 2022 · As series–parallel graphs have treewidth at most two, Theorem 5 implies that the connected treewidth of a series–parallel graph on n ...
[20]
[PDF] Bounding the Treewidth of Outer k-Planar Graphs via Triangulations
Abstract. The treewidth is a structural parameter that measures the tree-likeness of a graph. Many algorithmic and combinatorial results are expressed in ...
[21]
On triangulating k-outerplanar graphs - ScienceDirect.com
Jan 30, 2015 · 4. Treewidth of k -outerplanar graphs ... It is well-known that any k -outerplanar graph has treewidth at most 3 k − 1 [5], [6] and this bound is ...
[22]
[PDF] Chordal graphs with bounded tree-width - arXiv
Dec 31, 2022 · For chordal graphs one can show that the tree-width is equal to w − 1, hence bounding the tree-width by t is the same as bounding w by t + 1.
[23]
[PDF] Metric dimension parameterized by treewidth in chordal graphs - HAL
Jul 6, 2023 · Recall that, on chordal graphs, the treewidth is equal to the size of a maxi- mum clique minus one. Our proof is based on a dynamic programming ...
[24]
[PDF] Treewidth - LaBRI
"The treewidth of a graph G is the minimum, over all chordal supergraph H of G, of the size of a largest clique in H, minus 1 (that is ω(H)−1). 1. Page 2 ...
[25]
Graph minors. II. Algorithmic aspects of tree-width - ScienceDirect.com
We introduce an invariant of graphs called the tree-width, and use it to obtain a polynomially bounded algorithm to test if a graph has a subgraph contractible ...
[26]
Complexity of Finding Embeddings in a k-Tree
We determine the complexity status of two problems related to finding the smallest number k such that a given graph is a partial k-tree.
[27]
[2211.07154] An Improved Parameterized Algorithm for Treewidth
Nov 14, 2022 · We give an algorithm that takes as input an n-vertex graph G and an integer k, runs in time 2^{O(k^2)} n^{O(1)}, and outputs a tree decomposition of G of width ...
[28]
A Single-Exponential Time 2-Approximation Algorithm for Treewidth
Apr 15, 2021 · This is the first 2-approximation algorithm for treewidth that is faster than the known exact algorithms, and in particular improves upon the previous best ...
[29]
[2010.03105] An Improvement of Reed's Treewidth Approximation
Oct 7, 2020 · Abstract: We present a new approximation algorithm for the treewidth problem which constructs a corresponding tree decomposition as well.
[30]
Treewidth computations I. Upper bounds - ScienceDirect.com
This paper gives an overview of several upper bound heuristics that have been proposed and tested for the problem of determining the treewidth of a graph ...
[31]
Fast Algorithms for Join Operations on Tree Decompositions - arXiv
Jun 2, 2020 · Algorithms for problems on graphs of bounded treewidth mostly are dynamic programming algorithms using the structure of a tree decomposition of ...
[32]
https://www.sciencedirect.com/science/article/pii/S0890540109000947
[33]
[PDF] Algorithmic Meta-theorems for Restrictions of Treewidth
If the set variables are allowed to range over sets of vertices only then the logic is sometimes referred to as MSO1. A variation is MSO2 logic, where one is.
[34]
A Practical Approach to Courcelle's Theorem - ScienceDirect
The standard proof of Courcelle's Theorem is to construct a finite bottom-up tree automaton that recognizes a tree decomposition of the graph.Missing: limitations impractical derandomization
[35]
[PDF] Courcelle's Theorem: Overview and Applications
The treewidth of a graph is determined by the size of the tree decompositions of a graph, a way to define a graph with a tree structure. Definition 1.1.1 (Tree ...
[36]
Courcelle's Theorem: A Self-Contained Proof and a Path-Width Variant
May 1, 2024 · Courcelle's Theorem proves the existence of linear-time algorithms for decision problems on graphs with bounded tree-width.
[37]
[PDF] The treewidth and pathwidth of graph unions - arXiv
Sep 26, 2022 · Caterpillars have pathwidth 1, so the above lemma implies that two caterpillars can always be glued into a graph of pathwidth (and hence ...
[38]
[1606.06566] Faster Computation of Path-Width - arXiv
Jun 21, 2016 · Abstract:Tree-width and path-width are widely successful concepts. Many NP-hard problems have efficient solutions when restricted to graphs ...Missing: complete | Show results with:complete
[39]
[PDF] Bandwidth and pathwidth of three-dimensional grids - arXiv
Jan 5, 2011 · However, there is a close relation between the two parameters. In fact, it is known that the bandwidth of a graph is at least its pathwidth.
[40]
Pathwidth, Bandwidth, and Completion Problems to Proper Interval ...
Given an interval model for an interval graph with n vertices and an integer k, the algorithm constructs a layout of bandwidth at most k, if there exists one.
[41]
[PDF] Branchwidth of Graphs
Branchwidth was first defined by Robertson and Sey- mour in [25] and served as a main tool for their proof of Wagner's Conjecture in their Graph Minors series ...
[42]
[PDF] Branch-width and Tangles
Feb 21, 2010 · Branch-width, introduced by Robertson and Seymour [41], is a general concept to describe the difficulty of decomposing finitely many objects ...
[43]
[PDF] Call routing and the ratcatcher - Math (Princeton)
CALL ROUTING AND THE RATCATCHER. P. D. SEYMOUR, and R. THOMAS*. Received January 20, 1991. Revised February 10, 1993. Suppose we expect there to be p(ab) phone ...
[44]
[PDF] Branchwidth of graphic matroids. - HAL
Answering a question of Geelen, Gerards, Robertson and Whittle [2], we prove that the branchwidth of a bridgeless graph is equal to the branch- width of its ...
[45]
[PDF] Approximating clique-width and branch-width - Math (Princeton)
Abstract. We construct a polynomial-time algorithm to approximate the branch-width of certain symmetric submodular functions, and give two applications.
[46]
[PDF] Fast FPT-Approximation of Branchwidth - arXiv
Nov 5, 2021 · Oum and Seymour [38] proved that for any graph of rankwidth k, its cliquewidth is always between k and 2k+1 − 1. Moreover, their proof gives an ...
[47]
[PDF] bidimensional parameters and local treewidth - Erik Demaine
Applying Theorem 4.1 to P0 we obtain that, if F is of bounded local treewidth, then F has the parameter-treewidth property for P 0, which means that there ...Missing: global | Show results with:global
[48]
[PDF] Equivalence of Local Treewidth and Linear Local ... - Erik Demaine
For many NP-complete problems, we can derive polynomial-time algorithms restricted to graphs of bounded treewidth using a general dynamic-programming approach.
[49]
[PDF] STRUCTURE OF GRAPHS WITH LOCALLY RESTRICTED ...
Apr 25, 2017 · Graphs of low treewidth necessarily have small separators, and ... We now show that bounded local treewidth does not imply bounded layered.<|control11|><|separator|>
[50]
Treewidth -- from Wolfram MathWorld
The treewidth is a measure of the count of original graph vertices mapped onto any tree vertex in an optimal tree decomposition.
[51]
[PDF] Diameter and Treewidth in Minor-Closed Graph Families - arXiv
graphs of bounded genus, graphs of bounded treewidth, and graphs embeddable in R3 without any linked or knotted cycles. Definition 2. Define a family F of ...
[52]
On the treewidth of dynamic graphs - ScienceDirect.com
Oct 16, 2014 · Given a dynamic graph G, if G t has local treewidth (effectively) bounded by f ( r ) at each time t ∈ T ( G ) , then the Gaifman graph G ...Missing: global | Show results with:global
[53]
Testing first-order properties for subclasses of sparse graphs - arXiv
Sep 23, 2011 · We present a linear-time algorithm for deciding first-order (FO) properties in classes of graphs with bounded expansion.
[54]
[PDF] CS 7301.003.20F Lecture 18—October 19, 2020
The r x r grid has treewidth exactly r. But strangely, grids are essentially the only kinds of graphs with large treewidth. Theorem [R & S]: There is a function ...
[55]
Polynomial Bounds for the Grid-Minor Theorem | Journal of the ACM
In this article, we obtain the first polynomial relationship between treewidth and grid minor size by showing that f(k) = Ω(k δ ) for some fixed constant δ > 0.
[56]
[2410.19295] Treewidth, Hadwiger Number, and Induced Minors
Oct 25, 2024 · Treewidth and Hadwiger number are two of the most important parameters in structural graph theory. This paper studies graph classes in which ...
[57]
[PDF] Treedepth Inapproximability and Exponential ETH Lower Bound
Graphs of bounded treewidth famously lend themselves to fixed-parameter tractable (FPT) algorithms for various NP-hard problems, with parameter the width of the ...
[58]
[PDF] From tree-decompositions to clique-width terms - HAL
Nov 18, 2016 · In all our proofs that yield bounds on clique-width in terms of tree-width, ... Gurski and E. Wanke, Deciding clique-width for graphs of.
[59]
Improved Bounds for the Excluded-Minor Approximation of Treedepth
Abstract. Treedepth, a more restrictive graph width parameter than treewidth and pathwidth, plays a major role in the theory of sparse graph classes.Missing: advances | Show results with:advances
[60]
Treedepth Inapproximability and Exponential ETH Lower Bound
Jul 18, 2025 · Treedepth is a central parameter in graph theory. Computing it exactly is NP-complete, and 1.0003-approximation is NP-hard. Exact computation ...