Tree Decomposition

A tree decomposition of a graph G is a pair (T, β), where T is a tree and β (the 'bag' function) maps each node i of T to a subset β(i) of vertices of G, satisfying three key properties:

• Coverage: Every vertex of G is in at least one bag.
• Edge Coverage: For every edge (u,v) in G, there exists a bag containing both u and v.
• Running Intersection: For every vertex v of G, the set of tree nodes whose bags contain v forms a connected subtree of T.

The width of the decomposition is the size of the largest bag minus one. The treewidth of G is the minimum width across all possible tree decompositions.

Tree decomposition's power lies in transforming NP-hard problems on general graphs into problems solvable in polynomial time on trees of bounded width. The core mechanism is dynamic programming over the tree:

• Solve the problem locally within each bag, where the subgraph is small (bounded by treewidth).
• Propagate partial solutions up the tree, combining them at branch points.
• The running intersection property ensures consistency; a vertex's assignments are coordinated across all bags where it appears. For a Constraint Satisfaction Problem (CSP), this allows solving in time exponential only in the treewidth, but linear in the number of variables—making many real-world, sparse constraint graphs tractable.

In constraint processing, a tree decomposition of a CSP's constraint graph is often called a join tree or cluster tree. Here, each bag corresponds to the scope (set of variables) of one or more constraints. The decomposition enables junction tree algorithms for exact probabilistic inference in Bayesian networks and solving CSPs via bucket elimination. The process involves:

1. Moralization: For directed graphs (like Bayes nets), marry parents.
2. Triangulation: Add edges to make the graph chordal, ensuring a tree decomposition exists.
3. Forming Clusters: Create bags from maximal cliques of the triangulated graph.
4. Building the Tree: Connect clusters to satisfy the running intersection property.

Treewidth is the fundamental graph parameter that quantifies how 'tree-like' a graph is. It is defined as the minimum width of any tree decomposition.

• Trees have a treewidth of 1.
• Cycles have a treewidth of 2.
• A fully connected graph (clique) of n vertices has a treewidth of n-1. The complexity of many problems (e.g., CSP, inference, Hamiltonian path) shifts from exponential in the number of vertices to exponential in the treewidth. Finding the optimal tree decomposition (minimizing width) is itself NP-hard, but effective heuristic and approximation algorithms (e.g., minimum degree ordering) exist for constructing good decompositions in practice.

Tree decomposition is not merely theoretical; it underpins efficient solvers in multiple domains:

• Database Query Optimization: Complex SQL joins are optimized by viewing query graphs and finding efficient join orders via their treewidth.
• Probabilistic Graphical Models: The Hugin and Shenoy-Shafer algorithms for exact inference in Bayesian networks operate on a junction tree (a tree decomposition).
• Compiler Design: Register allocation can be modeled as a graph coloring problem on an interference graph; low treewidth makes it tractable.
• Bioinformatics: Analyzing phylogenetic networks and protein interaction networks.
• Sparse Matrix Computations: Determining efficient elimination orders for Gaussian elimination mirrors triangulation for tree decomposition.

Tree decomposition interacts closely with other advanced CSP and graph algorithms:

• Bucket Elimination: A variable elimination algorithm that implicitly creates a tree decomposition of the CSP's interaction graph. The order of elimination determines the treewidth.
• Clique Trees / Junction Trees: Specialized tree decompositions where bags are maximal cliques of a triangulated (chordal) graph.
• Treewidth-based Algorithms: A meta-algorithmic framework: if a problem can be expressed in Monadic Second-Order Logic (MSOL), it is fixed-parameter tractable with respect to treewidth (Courcelle's Theorem).
• Heuristic Decomposition Methods: In practice, solvers use heuristics like min-fill or maximum cardinality search to triangulate graphs and build decompositions of reasonable width.

Tree decomposition is the foundation for the junction tree algorithm, enabling exact inference in Bayesian networks and Markov random fields. The process involves:

• Moralizing the directed graph (for Bayesian networks).
• Triangulating the moral graph to create a chordal graph.
• Constructing a junction tree (join tree) from the maximal cliques.

Exact inference, such as computing marginal probabilities, becomes efficient (linear in the size of the junction tree) because the tree structure allows for localized message passing between clusters, avoiding exponential complexity on the original graph.

For CSPs whose constraint graph has bounded treewidth, tree decomposition enables solving via dynamic programming on the tree. The algorithm proceeds as follows:

• Each bag in the decomposition contains a subset of CSP variables.
• Dynamic programming tables store consistent partial assignments for each bag.
• Solutions are propagated from leaves to the root, combining compatible assignments from child bags.

This method can solve NP-hard CSPs like graph coloring or Boolean satisfiability in time exponential only in the treewidth, making it practical for problems with sparse, tree-like interaction structures common in scheduling and configuration.

The junction tree algorithm is a direct application of tree decomposition for probabilistic inference. Its key steps are:

1. Construction: Build a junction tree where each node is a clique (bag) of variables from the triangulated graph, satisfying the running intersection property.
2. Initialization: Assign potential functions (from CPTs or factors) to cliques.
3. Message Passing: Perform two rounds of sum-product or max-product message passing (collect and distribute) to achieve global consistency.
4. Marginalization: Compute marginals for any variable by focusing on a clique that contains it.

The treewidth of the underlying graph dictates the size of the largest clique, which is the primary driver of computational complexity.

Tree decomposition formalizes the concept of treewidth, a central parameter in parameterized complexity theory. A problem is fixed-parameter tractable (FPT) with respect to treewidth if it can be solved in time O(f(k) * n^c), where:

• k is the treewidth.
• f is a computable function (typically exponential).
• n is the input size.
• c is a constant.

This means that for instances with small, bounded treewidth (e.g., < 10), many NP-hard problems become practically solvable. This framework is used to analyze and design algorithms for problems in databases (e.g., evaluating conjunctive queries), computational biology, and model checking.

Treewidth is part of a hierarchy of graph width parameters that measure how "tree-like" a graph is. Understanding these relations helps select the right algorithmic strategy:

• Treewidth: Measures decomposability into a tree. Bounded treewidth enables dynamic programming.
• Pathwidth: A more restrictive measure where the decomposition must be a path. Algorithms are often simpler.
• Branchwidth: A parameter closely related to treewidth, often used in planar graph algorithms.
• Clique-width: Measures complexity via graph operations; different from but related to treewidth for dense graphs.

Problems on graphs with low treewidth but high clique-width may still be hard, guiding algorithm selection in combinatorial optimization.

While finding an optimal tree decomposition of minimum width is itself NP-hard, practical constraint and SAT solvers use heuristic decomposition methods. These are crucial for handling real-world instances:

• Minimum Degree Elimination: A greedy heuristic that simulates variable elimination, producing a triangulation and corresponding decomposition.
• Maximum Cardinality Search: Another greedy algorithm used to recognize chordal graphs and find cliques.
• Integration in Solvers: Tools like Gecode and OR-Tools can exploit problem structure. SAT solvers using Conflict-Driven Clause Learning (CDCL) implicitly manage a form of decomposition through their variable interaction graph.

These heuristics allow the application of tree decomposition techniques to problems where the perfect, minimal-width tree is not required for significant performance gains.

Treewidth is a fundamental graph parameter that quantifies how 'tree-like' a graph is. It is defined as the minimum width (size of the largest node minus one) across all possible tree decompositions of a graph. A low treewidth indicates the graph's structure can be efficiently captured by a tree, which is the precondition for using tree decomposition to solve NP-hard problems in polynomial time. For example, many real-world problems in areas like computational biology or scheduling have bounded, low treewidth, making them amenable to dynamic programming on a tree decomposition.

A clique tree or junction tree is a specific type of tree decomposition where the nodes (called 'bags') are maximal cliques of the original graph. This structure is central to the junction tree algorithm for exact inference in probabilistic graphical models like Bayesian networks. The algorithm works by:

• Constructing a junction tree from the moralized graph.
• Performing message passing between cliques.
• Marginalizing distributions to compute probabilities. It ensures that the running intersection property is satisfied, guaranteeing correct, global consistency after local computations.

A chordal graph (or triangulated graph) is an undirected graph in which every cycle of length four or greater has a chord—an edge connecting two non-consecutive vertices in the cycle. Chordal graphs are critically important because:

• They are the prerequisite structure for constructing a junction tree; a graph must be chordalized (triangulated) before a valid junction tree can be built.
• The treewidth of a chordal graph is the size of its largest clique minus one.
• Many algorithms for tree decomposition first triangulate the constraint graph, adding necessary edges to make it chordal, which can increase the treewidth.

This is the primary algorithmic technique that leverages a tree decomposition to solve problems. Once a graph is mapped to a tree structure with bounded bag size, a bottom-up dynamic programming algorithm can be executed. The process involves:

• Defining a state for each partial solution within a bag.
• Computing a table of possible states for each tree node.
• Combining child table results into the parent table via a join operation.
• Propagating solutions up the tree to the root. This transforms an exponential problem on the original graph into one solvable in time exponential only in the treewidth, but polynomial in the graph size.

Hypertree decomposition is a generalization of tree decomposition designed for hypergraphs, which are common in representing constraints involving more than two variables (non-binary CSPs). It decomposes a hypergraph into a tree of connected sub-hypergraphs. Key properties include:

• It defines hypertree width, a more powerful measure than treewidth for hypergraphs.
• Constraint Satisfaction Problems with bounded hypertree width are polynomial-time solvable.
• It is the basis for efficient evaluation of database conjunctive queries, where each query atom is a hyperedge.

A path decomposition is a special case of a tree decomposition where the underlying tree structure is a simple path. This imposes a stricter, linear ordering on the bags. Concepts include:

• Pathwidth: The analog to treewidth for path decompositions. It is always at least as large as the treewidth.
• Problems on graphs with bounded pathwidth are often solvable with simpler linear-time dynamic programming.
• Many algorithmic meta-theorems state that problems expressible in certain logics can be solved efficiently on graphs of bounded pathwidth.