Tree Decompositions in Julia

Tree Decompositions

Let G = (V_G, E_G) be a simple graph and B = \{B_1, \dots, B_n\} a family of subsets B_i \subseteq V_G. Then a tree T = (B, E_T) is called a tree decomposition of G—also a junction tree, join tree, or clique tree—if it satisfies the following properties.

1. For all vertices v \in V_G, the set \{ B_i \in B \mid v \in B_i \} induces a nonempty connected subgraph of T.

2. For all edges \{v, w\} \in E_G, the set \{ B_i \in B \mid v \in B_i \text{ and } w \in B_i\} is nonempty.

The width of a tree decomposition T is the number \tau := \max \{ \lvert B_i \rvert \mid B_i \in B \} - 1, and the treewidth of a graph is the width of its smallest tree decomposition. Tree decompositions of small width are highly desirable, for they can be used to implement fast algorithms on graphs and graph structured data. To see how this works, we will look at an example from dynamic programming in the next section.

Dynamic Programming

Suppose we want to minimize a function f: X \times Y \times Z \to \mathbb{R} where \lvert X \rvert = \lvert Y \rvert = \lvert Z \rvert = n. Since X, Y, and Z are finite sets, we can find the minimum in n^3 time by enumerating every triple (x, y, z) \in X \times Y \times Z. In general, there is no faster solution. However, if f is of the form f = g + h for some functions \begin{aligned} g: X \times Y &\to \mathbb{R}\\ h: Y \times Z &\to \mathbb{R}\\ \end{aligned} then we can do the following. For all y \in Y, we compute and record the number h^*(y) := \min \{ h(y, z) \mid z \in Z \}. Then we compute the minimum of the sum g(x, y) + h^*(y). Both quantities can be computed in n^2 time, so the time complexity of the second procedure is n^2. What we have done is take advantage of the fact that the variables x and z are not directly coupled, but rather related to each other via the variable y. Another way of expressing this observation is to state that the interaction graph of f admits the following tree decomposition.

This trick is generalized by Algorithm 7.1 in Vandenberghe and Andersen, 2015, which computes the minimum of a function f: X_1 \times \dots \times X_n \to \mathbb{R} of the form f = \sum_{i = 1}^m f_i The algorithm takes a tree decomposition as one of its input parameters, and its runtime is determinded by the width of the decomposition.

Other Applications

Perhaps the most sucessful application of tree decompositions to numerical computing is in sparse matrix software. Libraries like SuiteSparse and HSL construct tree decompositions during the symbolic factorization stge of their Cholesky and LU factorization routines. Other applications include

• convex optimization
• tensor network contraction
• probabilistic inference

all of which are present in the Julia ecosystem in packages like Clarabel.jl, OMEinsumContractionOrders.jl, and JunctionTrees.jl.

Engineering

Let G = (V_G, E_G) be a simple graph. Every permutation \sigma: V_G \to V_G on the vertices of G induces a tree decomposition on G via a procedure called vertex elimination. Furthermore, the induced tree decomposition can be computed in almost-linear time, and the implementation in CliqueTrees.jl is in practice extremely fast. Hence, the problem of finding a tree decomposition of G can be reduced to the problem of finding a permutation of V_G. CliqueTrees.jl implements a number of algorithms for solving this problem.

Several more algorithms are implemented as package extensions.

This list includes exact, exponential-time algorithms like BT and SAT, which are guaranteed to create decompositions of minimal width, as well as linear-time heuristic algorithms like AMF and AMD that can decompose graphs with millions of vertices. Other algorithms, like MinimalChordal and RuleReduction are pre or post-processors; they are parametrized by another algorithm and work by transforming its input or output. These meta-algorithms are useful enough that some packages prefer to call their own tree decomposition algorithms through CliqueTrees.jl.

Coming Soon

In a subsequent blog post, I will discuss a categorification of tree decompositions called structured decompositions.