Skip to content

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.

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.

Scope of Application

  • 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.

  • 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.

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.

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.

Abstract Reasoning

  1. Type the carrier. Identify the graph theory entities to which the claim applies.
  2. 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.
  3. Check operation and conditions.

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.

Relationships to Other Abstractions

Local relationship map for Tree DecompositionParents appear above the current abstraction, mutual partners to the right, and children below. Node labels state whether each abstraction is prime or domain-specific; colors identify relation types.Tree DecompositionDOMAINPrime abstraction: Decomposition — presupposesDecompositionPRIME

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

Neighborhood in Abstraction Space

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

Family — Data Structures & Graph Variants (17 abstractions)

Nearest neighbors

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