Is this the same as a spanning tree?

No. A spanning tree uses original vertices and selected original edges; a decomposition tree connects bags.

Can one vertex appear in many bags?

Yes, provided those bags form a connected subtree.

Must the decomposition have minimum width?

No. Any valid decomposition can be used, although its width affects the cost of many algorithms.

AI Glossary / Graphs and symbolic AI / Advanced

Tree decomposition

Definition

A tree decomposition represents a graph as overlapping groups of vertices, called bags, connected in a tree. The bags must cover the original graph and keep every vertex's appearances connected. This structure supports algorithms that solve local subproblems and coordinate their shared information.

What it means

A graph can contain cycles even when its decomposition has a tree shape. The tree connects bags of vertices, not necessarily individual vertices from the original graph. This distinction lets an algorithm organize a complicated network without deleting relationships that affect the answer.

In constraint satisfaction, vertices can represent variables and edges can represent constraints between pairs. A bag groups several variables into a local subproblem. Neighboring bags exchange information about variables they share.

The overlap is essential. It preserves dependencies between subproblems, while the tree structure provides a manageable route for combining their results. Separately finding one solution for each bag is insufficient if those chosen solutions disagree on a shared variable.

How it works

Three conditions define a valid decomposition. Every original vertex must occur in at least one bag. Both endpoints of every original edge must occur together in at least one bag. Finally, the bags containing any particular vertex must form a connected part of the decomposition tree. The last condition is often called the running-intersection property.

For a finite-domain constraint problem, a local table can record assignments that satisfy the constraints represented in a bag. Information passes between adjacent bags using their shared variables. Assignments with no compatible continuation can be discarded; compatible choices can be assembled into a global solution.

The largest bag strongly influences the amount of local information. The width of a decomposition is its largest bag size minus one. A single bag containing every vertex is valid, but often offers little computational advantage. Finding a useful decomposition is therefore a separate part of the solving process.

Three practical examples

A configuration system groups interdependent product options and passes compatibility information through shared options.
A probabilistic inference system organizes related variables into a tree of clusters so that local calculations can be coordinated.
A graph-algorithm researcher evaluates whether a problem can be solved efficiently when a small-width decomposition is supplied.

Think of it this way

Think of project teams with overlapping responsibilities. Each team handles a manageable set of decisions, but a shared decision must remain consistent across every team that depends on it.

The analogy stops at the mathematical requirements. An ordinary organization chart does not automatically satisfy coverage or running intersection. A tree decomposition is a precisely checked representation, not simply any diagram showing teams and reporting lines.

Worked example

Decomposing a four-variable cycle

Let the graph have vertices A, B, C and D, with edges AB, BC, CD and DA. Create two bags, {A,B,C} and {A,C,D}, joined by one tree edge.

All four vertices occur. The first bag covers AB and BC; the second covers CD and DA. A and C appear in both adjacent bags, so their occurrences are connected. B and D each occur once. The decomposition is valid, with width 3−1=2. A and C may share a bag even though AC is not an original edge.

For binary variables, suppose every cycle edge requires its endpoints to differ. The first bag permits assignments 010 and 101 in A,B,C order. The second permits 001 and 110 in A,C,D order. Matching shared values A,C gives global assignments 0101 and 1010 in A,B,C,D order.

Choosing 010 from the first bag and 110 from the second would disagree on A and C. Local validity alone does not permit that combination. The overlap agreement is what makes reconstruction work.

Illustrative case study

Fictional Maple Configurations divides a product-options problem into several groups. Its first prototype solves each group independently, then discovers that different groups select incompatible values for the same power option.

The team rebuilds the representation as a valid tree decomposition. Shared variables appear along connected paths, and the solver retains compatible local alternatives instead of committing prematurely to one local answer.

A review also identifies a large bag created by an unfortunate grouping choice. The team evaluates a different decomposition before claiming a performance benefit. The fictional case illustrates representation and consistency checks; it does not establish a measured speedup or imply that every configuration problem has small bags.

Common misconceptions and mistakes

A tree decomposition removes enough original edges to leave a tree. It preserves edge coverage by grouping vertices; deleting constraints would change the problem.
Bags must be disjoint. Overlap is normally necessary to preserve relationships.
Any tree of covering bags is valid. The connected-occurrence condition for each vertex must also hold.

Business use

Tree decomposition can help explain why some highly connected-looking problems remain manageable while others require very large intermediate tables. The practical opportunity depends on bag sizes, variable domains, constraint representation and decomposition overhead.

Ask whether the decomposition is valid, how it was obtained and which information is exchanged across shared variables. Compare total solving time and memory, including preparation. A narrow-looking drawing is not evidence of low width, and a valid decomposition is not a guarantee of a commercially useful speedup.

Check your understanding

A vertex X appears in the first and third bags along a three-bag path, but not in the middle bag. Is the decomposition valid?

Answer: No. The bags containing X are disconnected. X must also appear in the intervening bag, or the decomposition must be reorganized.

Related terms

Tree width
Constraint satisfaction problem
Dynamic programming
Variable elimination
running-intersection property
separator
junction tree

Learn next

Read tree width and variable elimination. Draw a cycle, construct the two-bag decomposition above, and check coverage and connected occurrences before attempting any local calculations.

Sources

Russell and Norvig, Constraint Satisfaction Problems, author-hosted chapter, Section 5.4 on tree decomposition and agreement between shared variables: https://aima.cs.berkeley.edu/4th-ed/pdfs/newchap05.pdf

The relevant primary textbook section and its decomposition requirements were read. The binary-cycle example, assignment lists and fictional case are original illustrations checked directly. No solver execution or general empirical speedup is claimed.

Previous: Tree contraction Next: Tree-like search