Tree Decomposition¶

In graph theory, a tree decomposition is a mapping of a graph into a tree that can be used to define the treewidth of the graph and speed up solving certain computational problems on the graph.

Version: v1 · 2026-09-28 · History
Domain-specific #: 8497
Domain group: Formal Sciences
Origin domain: Mathematics
Subdomains: Graph Theory, Treewidth → Mathematics

Core Idea¶

Tree Decomposition is treated here as the recurring graph theory identity summarized by this source-grounded definition: In graph theory, a tree decomposition is a mapping of a graph into a tree that can be used to define the treewidth of the graph and speed up solving certain computational problems on the graph.

In graph theory, a tree decomposition is a mapping of a graph into a tree that can be used to define the treewidth of the graph and speed up solving certain computational problems on the graph. Tree decompositions are also called junction trees, clique trees, or join trees. They play an important role in problems like probabilistic inference, constraint satisfaction, query optimization, and matrix decomposition.

The concept of tree decomposition was originally introduced by . Later it was rediscovered by and has since been studied by many other authors. Thus, given a graph , a tree decomposition is a pair , where is a family of subsets (sometimes called bags) of , and is a tree whose nodes are the subsets , satisfying the following properties.

For Tree Decomposition, the abstraction is narrower than the article's general subject matter: a positive case must preserve In graph theory, a tree decomposition is a mapping of a graph into a tree that can be used to define the treewidth of the graph and speed up solving certain computational problems on the graph. Retaining only the name, a familiar example, or a downstream effect is insufficient. The specialist roles and tests remain anchored in graph theory, which is why this identity is domain-specific rather than prime.

How would you explain it like I'm…

Dots in Bags on a Tree

Take a dot-and-line drawing and put its dots into little bags. The bags are hooked together like the branches of a tree, and each line of the drawing must fit inside at least one bag. Keeping the bags small makes some hard puzzles about the drawing much faster to solve.

Graph Bags on a Tree

A tree decomposition takes a graph, a network of dots and lines, and organizes it into small groups of dots called bags, arranged in a tree shape. The groups can overlap. The rules make sure every dot and every line of the original graph is inside some bag, and that the bags holding any one dot are all connected together in the tree. If you can use small bags, the graph is 'tree-like,' and many hard problems become much faster to solve. It is also called a junction tree, clique tree, or join tree.

Bags-and-Tree Graph Mapping

In graph theory, a tree decomposition maps a graph onto a tree so that the graph's structure can be handled piece by piece. It consists of a tree whose nodes are 'bags', subsets of the graph's vertices, satisfying three conditions: every vertex lies in at least one bag, both endpoints of every edge appear together in some bag, and for each vertex the bags containing it form a connected subtree. The width is the size of the largest bag minus one, and the treewidth of the graph is the smallest width over all its tree decompositions. When treewidth is small, many hard computational problems become efficiently solvable by working along the tree. Tree decompositions are also known as junction trees, clique trees, or join trees, and they matter in probabilistic inference, constraint satisfaction, database query optimization, and matrix decomposition.

A tree decomposition of a graph G is a pair consisting of a family of vertex subsets, called bags, and a tree whose nodes correspond to those bags, satisfying: every vertex of G lies in at least one bag; for every edge, some bag contains both endpoints; and for every vertex, the tree nodes whose bags contain it induce a connected subtree. It is a mapping of the graph into a tree that captures how tree-like the graph is. Its width is the largest bag size minus one, and the treewidth of G is the minimum width over all tree decompositions. Because separators are organized along the tree, dynamic programming over the decomposition solves many otherwise hard problems efficiently on bounded-treewidth graphs. The same object recurs as junction trees, clique trees, and join trees in probabilistic inference, constraint satisfaction, query optimization, and sparse matrix decomposition. The concept is this bag-and-tree structure with its conditions, not merely any use of trees in graph algorithms.

Structural Signature¶

Sig role-phrases:

Defining carrier — The size of the maximum independent set is the largest value stored at the root node, and the maximum independent set itself can be found (as is standard in dynamic programming algorithms) by backtracking through these stored values starting from this largest value.
Constitutive relation — In this definition, the size of the largest set is diminished by one in order to make the treewidth of a tree equal to one.
Operating condition — At the beginning of the 1970s, it was observed that a large class of combinatorial optimization problems defined on graphs could be efficiently solved by non-serial dynamic programming as long as the graph had a bounded dimension, a parameter related to treewidth.
Recognition evidence — Later, several authors independently observed, at the end of the 1980s, that many algorithmic problems that are NP-complete for arbitrary graphs may be solved efficiently by dynamic programming for graphs of bounded treewidth, using the tree-decompositions of these graphs.
Admissible variation — We may calculate these and values by a bottom-up traversal of the tree.
Characteristic consequence — Later it was rediscovered by and has since been studied by many other authors.
Failure boundary — The concept of tree decomposition was originally introduced by .

What It Is Not¶

Not the whole field of graph theory. The node requires the specific identity stated by In graph theory, a tree decomposition is a mapping of a graph into a tree that can be used to define the treewidth of the graph and speed up solving certain computational problems on the graph.
Not an over-broad reading. However, when is any fixed constant, the graphs with treewidth can be recognized, and a width tree decomposition constructed for them, in linear time.
Not an over-broad reading. Intuitively, a tree decomposition represents the vertices of a given graph as subtrees of a tree, in such a way that vertices in are adjacent only when the corresponding subtrees intersect.
Not an over-broad reading. Each subtree associates a graph vertex with a set of tree nodes.
Not automatically Treewidth. Retrieval proximity does not establish equivalence; the two identities must be compared by carrier, operation, and failure boundary.

Scope of Application¶

Tree Decomposition applies literally inside graph theory wherever the source-defined carrier and relation can be established. Its documented habitats include:

Treewidth. The time dependence of this algorithm on is an exponential function of .
Dynamic programming. This dynamic programming approach is used in machine learning via the junction tree algorithm for belief propagation in graphs of bounded treewidth.
Documented setting. In graph theory, a tree decomposition is a mapping of a graph into a tree that can be used to define the treewidth of the graph and speed up solving certain computational problems on the graph.
Definition. Intuitively, a tree decomposition represents the vertices of a given graph as subtrees of a tree, in such a way that vertices in are adjacent only when the corresponding subtrees intersect.
Definition. Each subtree associates a graph vertex with a set of tree nodes.
Definition. To define this formally, we represent each tree node as the set of vertices associated with it.

Outside graph theory, the name should be retained only when these same operational conditions survive; otherwise the comparison belongs to the broader parent Decomposition or should be marked as analogy.

Clarity¶

A clear use of Tree Decomposition names the carrier, the operative relation, and the conditions under which the source treats the identity as present. The minimal definition is In graph theory, a tree decomposition is a mapping of a graph into a tree that can be used to define the treewidth of the graph and speed up solving certain computational problems on the graph. The strongest recognition evidence in the frozen account is: Later, several authors independently observed, at the end of the 1980s, that many algorithmic problems that are NP-complete for arbitrary graphs may be solved efficiently by dynamic programming for graphs of bounded treewidth, using the tree-decompositions of these graphs. A report should distinguish that evidence from a proxy, consequence, or common implementation. It should also state the qualification However, when is any fixed constant, the graphs with treewidth can be recognized, and a width tree decomposition constructed for them, in linear time. so that a reader can reproduce the classification rather than infer it from topical resemblance.

Manages Complexity¶

Tree Decomposition compresses multiple graph theory details into a stable diagnostic relation. The source shows both the central mechanism—in this definition, the size of the largest set is diminished by one in order to make the treewidth of a tree equal to one.—and the practical consequence—later it was rediscovered by and has since been studied by many other authors. This compression makes cases comparable while leaving parameters, conventions, exceptions, and evidential quality explicit. It is lossy by design: local history and implementation details may be omitted only when they do not alter the defining relation.

Abstract Reasoning¶

Type the carrier. Identify the graph theory entities to which the claim applies.
State the relation. Use the source-grounded identity: In graph theory, a tree decomposition is a mapping of a graph into a tree that can be used to define the treewidth of the graph and speed up solving certain computational problems on the graph.
Check operation and conditions. At the beginning of the 1970s, it was observed that a large class of combinatorial optimization problems defined on graphs could be efficiently solved by non-serial dynamic programming as long as the graph had a bounded dimension, a parameter related to treewidth.
Demand recognition evidence. Later, several authors independently observed, at the end of the 1980s, that many algorithmic problems that are NP-complete for arbitrary graphs may be solved efficiently by dynamic programming for graphs of bounded treewidth, using the tree-decompositions of these graphs.
Test variation. Change an implementation or setting while preserving we may calculate these and values by a bottom-up traversal of the tree.
Run the collapse test. Remove the defining operation; if the label still seems equally apt, only a topic or correlate was retained.
Reduce cautiously. When the specialist conditions cannot be carried, route the residual comparison to Decomposition.

Knowledge Transfer¶

Within the home domain. Knowledge about Tree Decomposition transfers literally when a new case preserves the same carrier type, relation, and recognition test. The time dependence of this algorithm on is an exponential function of . This dynamic programming approach is used in machine learning via the junction tree algorithm for belief propagation in graphs of bounded treewidth.

Beyond the home domain. Transfer the broader Decomposition relation when the graph theory-specific differentia cannot be filled. Retain the name Tree Decomposition only when the same carrier, operation, and rejection conditions are present literally rather than metaphorically.

Examples¶

Canonical¶

The tree decomposition of a graph is far from unique; for example, a trivial tree decomposition contains all vertices of the graph in its single root node. This case is canonical because it supplies a concrete carrier and lets the defining relation be checked rather than merely named.

Mapped back: carrier → the entities in the documented case; operation → In graph theory, a tree decomposition is a mapping of a graph into a tree that can be used to define the treewidth of the graph and speed up solving certain computational problems on the graph; recognition evidence → Later, several authors independently observed, at the end of the 1980s, that many algorithmic problems that are NP-complete for arbitrary graphs may be solved efficiently by dynamic programming for graphs of bounded treewidth, using the tree-decompositions of these graphs

Applied / In Practice¶

Treewidth may also be defined from other structures than tree decompositions, including chordal graphs, brambles, and havens. The applied case shows how the identity is used under a second setting or qualification while keeping the same operative relation.

Mapped back: changed setting → Treewidth; invariant → In graph theory, a tree decomposition is a mapping of a graph into a tree that can be used to define the treewidth of the graph and speed up solving certain computational problems on the graph; boundary → the case exits the class when however, when is any fixed constant, the graphs with treewidth can be recognized, and a width tree decomposition constructed for them, in linear time

Structural Tensions¶

T1 — Stable identity versus admissible variation. However, when is any fixed constant, the graphs with treewidth can be recognized, and a width tree decomposition constructed for them, in linear time. The tension matters because emphasizing only one side either dissolves the identity or overstates what the evidence and domain conventions warrant.

Diagnostic: Which changes preserve the defining relation, and which replace it?

T2 — Recognition versus proxy. Intuitively, a tree decomposition represents the vertices of a given graph as subtrees of a tree, in such a way that vertices in are adjacent only when the corresponding subtrees intersect. The tension matters because emphasizing only one side either dissolves the identity or overstates what the evidence and domain conventions warrant.

Diagnostic: Does the cited evidence establish the identity or only a correlated sign?

T3 — Definition versus implementation. Each subtree associates a graph vertex with a set of tree nodes. The tension matters because emphasizing only one side either dissolves the identity or overstates what the evidence and domain conventions warrant.

Diagnostic: Is the observed implementation constitutive, optional, or merely common?

T4 — Scope versus overextension. To define this formally, we represent each tree node as the set of vertices associated with it. The tension matters because emphasizing only one side either dissolves the identity or overstates what the evidence and domain conventions warrant.

Diagnostic: Can every claimed application fill the same typed roles without metaphor?

T5 — Transfer versus domain accent. The size of the maximum independent set is the largest value stored at the root node, and the maximum independent set itself can be found (as is standard in dynamic programming algorithms) by backtracking through these stored values starting from this largest value. The tension matters because emphasizing only one side either dissolves the identity or overstates what the evidence and domain conventions warrant.

Diagnostic: Does the receiving case instantiate Tree Decomposition literally, co-instantiate Decomposition, or only resemble it?

T6 — Autonomy versus reduction. In this definition, the size of the largest set is diminished by one in order to make the treewidth of a tree equal to one. The tension matters because emphasizing only one side either dissolves the identity or overstates what the evidence and domain conventions warrant.

Diagnostic: What does Tree Decomposition distinguish that the broader parent Decomposition leaves together?

Structural–Framed Character¶

Tree Decomposition is mixed or framed-leaning. Its structural side is the repeatable organization summarized by In graph theory, a tree decomposition is a mapping of a graph into a tree that can be used to define the treewidth of the graph and speed up solving certain computational problems on the graph. Its framed side is the graph theory vocabulary that fixes the carrier, evidence, exceptions, and admissible transformations.

Evaluative weight: the identity can be stated descriptively even when applications carry practical stakes. Human-practice dependence: the source-grounded carrier determines whether the relation exists independently or is constituted by a practice. Institutional origin: disciplinary conventions stabilize the name and test. Vocabulary portability: At the beginning of the 1970s, it was observed that a large class of combinatorial optimization problems defined on graphs could be efficiently solved by non-serial dynamic programming as long as the graph had a bounded dimension, a parameter related to treewidth. Import versus recognition: literal transfer requires the same mechanism; shape alone is analogy.

Its portable skeleton is Decomposition. Its character: a recurring specialist identity whose thin organization can be abstracted, while its operational meaning remains domain-bound.

Structural Core vs. Domain Accent¶

What is skeletal. In graph theory, a tree decomposition is a mapping of a graph into a tree that can be used to define the treewidth of the graph and speed up solving certain computational problems on the graph. The reviewed portable genus is Decomposition; the candidate preserves that parent relation across admissible variants. The source-grounded carrier and relation are expressed by these conditions: The size of the maximum independent set is the largest value stored at the root node, and the maximum independent set itself can be found (as is standard in dynamic programming algorithms) by backtracking through these stored values starting from this largest value. In this definition, the size of the largest set is diminished by one in order to make the treewidth of a tree equal to one. The recognition and variation tests add: At the beginning of the 1970s, it was observed that a large class of combinatorial optimization problems defined on graphs could be efficiently solved by non-serial dynamic programming as long as the graph had a bounded dimension, a parameter related to treewidth. Later, several authors independently observed, at the end of the 1980s, that many algorithmic problems that are NP-complete for arbitrary graphs may be solved efficiently by dynamic programming for graphs of bounded treewidth, using the tree-decompositions of these graphs.

What is domain-bound. graph theory fixes the carrier, technical vocabulary, admissible evidence, and exceptions that distinguish Tree Decomposition from other Decomposition instances. Its documented habitat includes the condition that The time dependence of this algorithm on is an exponential function of . A second source-grounded application condition is that This dynamic programming approach is used in machine learning via the junction tree algorithm for belief propagation in graphs of bounded treewidth. Those details determine what the words denote, what observations warrant classification, and which apparent similarities are false positives.

Why the node remains domain-specific. Removing the graph theory differentia leaves the parent rather than the candidate. The edge records that reduction without claiming that every topical neighbor is hierarchical. The final collapse test is source-specific: We may calculate these and values by a bottom-up traversal of the tree. If that condition or the defining relation is absent, the case may instantiate Decomposition, but it is not Tree Decomposition.

This entry presupposes Decomposition.

Immediate parent — Decomposition (Composition). Tree Decomposition structurally presupposes Decomposition. Tree Decomposition structurally presupposes Decomposition: In graph theory, a tree decomposition is a mapping of a graph into a tree that can be used to define the treewidth of the graph and speed up solving certain computational problems on the graph. The candidate cannot be specified without the parent operation—Breaking a whole into parts that can be analyzed independently and recombined to reconstitute the whole, making complexity tractable through divide-and-conquer.—but is not itself a subtype of that operation.
Other nearby abstractions. Retrieval neighbors remain comparison surfaces only; no additional parent is asserted without a necessary-genus or structural-prerequisite test.

Relationships to Other Abstractions¶

Current abstraction Tree Decomposition Domain-specific

Parents (1) — more general patterns this builds on

Tree Decomposition presupposes Decomposition Prime

Tree Decomposition structurally presupposes Decomposition: In graph theory, a tree decomposition is a mapping of a graph into a tree that can be used to define the treewidth of the graph and speed up solving certain computational problems on the graph.

Hierarchy path (1) — routes to 1 parentless root

Tree Decomposition → Decomposition

Neighborhood in Abstraction Space¶

Tree Decomposition sits in a moderately populated region (49^th percentile for distinctiveness): it has near-neighbors but no dense thicket of look-alikes.

Family — Data Structures & Graph Variants (17 abstractions)

Nearest neighbors

Maximal independent set — 0.88
Game complexity — 0.87
NC (complexity) — 0.87
Tractable Problem — 0.86
Skip list — 0.85

Computed from structural-signature embeddings · 2026-10-08

Not to Be Confused With¶

Decomposition. The parent omits the specialist differentia. Tell: Can the case establish In graph theory, a tree decomposition is a mapping of a graph into a tree that can be used to define the treewidth of the graph and speed up solving certain computational problems on the graph?
Treewidth. The minimum, over all tree decompositions of a graph, of the largest bag size minus one, measuring how closely the graph can be organized around tree-like separators. Tell: Which entry's carrier, operation, and failure condition are satisfied?
SPQR Tree. A canonical tree representation of a biconnected graph's decomposition at separation pairs, whose S, P, Q, and R skeletons expose series, parallel, edge, and rigid triconnected structure and reconstruct the graph through paired virtual edges. Tell: Which entry's carrier, operation, and failure condition are satisfied?
Partial k-tree. A graph that embeds as a subgraph of a k-tree, equivalently one whose treewidth is at most k. Tell: Which entry's carrier, operation, and failure condition are satisfied?
A measurement, proxy, or consequence. Those may provide evidence without being the identity. Tell: Would Tree Decomposition remain present if the detector or downstream effect changed?
A metaphorical analogue. A similar shape outside graph theory lacks the specialist mechanism. Tell: Do the native roles transfer literally, or only the parent Decomposition?

References¶

Frozen Wikipedia discovery revision: https://en.wikipedia.org/wiki/Tree_decomposition (revision 1369223734).
Preserved source candidate: http://www.math.uni-hamburg.de/home/diestel/books/graph.theory/

The frozen Wikipedia revision is discovery provenance. The retained source set was reviewed for identity, formal or operational relation, and scope. The encyclopedia's structural synthesis is bounded to those claims; a thin authority surface is recorded as a nonblocking source-strengthening repair rather than concealed.