Compositional Algorithms

I’m fascinated by compositionality, the study of how the whole can be determined by its parts.

Category theorists will tell you that this topic sits entirely within their domain… and they’re not wrong, but fundamentally I think that most of mathematics has to do with some sort of compositionality.

One particular flavor of compositionality that interests me is that found in discrete mathematics; particualrly in graph theory and algorithms. This post will be the first in a series on compositional structure in graph theory and complexity theory.

Algorithms on recursive structure

Compositionality in complexity theory usually consists of exploiting some compositional structure of the input data. Trees are the prototypical example of recursive structure and, unsurprisingly, algorithms that compute on trees are usually compositional.

The rest of this post will use the pretext of solving the Weighted Independet Set problem on trees to set the scene for what is to come in the future.

The task is to find a vertex-subset $I$ of some input vertex-weighted tree $(T, w: V(T) \to \mathbb{N})$ which has maximum weight such that that no two vertices of $I$ are adjacent in $T$ .

The compositional structure of trees comes in handy: trees can be built from smaller trees by glueing along shared copies of $K_1$ (the 1-vertex complete graph; I’ll abbreviate it simply as “ $1$ “). In category theory this is called a pushout; I’ll adopt this notation here: pick two vertices of two trees $T_1$ and $T_2$ — by choosing homomorphisms $T_1 \hookleftarrow 1 \hookrightarrow T_2$ — then the pushout of this diagram is the tree $T_1 +_{1} T_2$ obtained by “gluing” the image of $K_1$ in $T_1$ to its image in $T_2$ .

Anyway, back to the weighted independet set. How does the compositional structure of trees help us solve our problem?

Well, suppose the input is given as the gluing $T_1 +_{1} T_2$ along some “root’ vertex $r$ and suppose further that we already computed all of the independent sets in $T_1$ and $T_2$ — let’s call these $\mathcal{I}_1$ and $\mathcal{I}_2$ –, then we observe that we can compute all of the independent sets in $T$ by matching-up the independent sets of $\mathcal{I}_1$ with those of $\mathcal{I}_2$ . Explicitly, given any two independent sets $\iota_1$ and $\iota_2$ in $\mathcal{I}_1$ and $\mathcal{I}_2$ , they can be combined into an independent set for $T$ iff $(\iota_1 \cup \iota_2)|_{N(r) \cup \{r\}}$ is an independent set in the closed neighborhood of $r$ (the vertex we glued the two trees along).

Now, even if you perhaps find this neat, you’re probably asking yourself two questions: (1) “why are we enumerating all independent sets? doesn’t this make the algorithm very slow?” and (2) “why can’t we just keep track of the biggest independent set on each side?” .. well, I’m glad you asked!

The second question has an easy answer which you can figure out for yourself by staring at this picture:

If we only kept track of the best solution on the RHS and LHS, then we might never find the global optimum (1002 in the example above). This also provides a partial answer to the first question: we need to keep track of all solutions in the LHS and RHS simply because we prefer correct algorithms over incorrect ones.

Now the question about speed is a good one. The algorithm above is very slow. Let’s improve it!

Notice that, when we composed the partial solutions $\iota_1$ and $\iota_2$ , we only needed to check that their union gave us an independent set locally (i.e. on the closed neighborhood of $r$ ) in order to deduce that we could compose them. This suggests that we’re carying around way too much information: we don’t need to compute all of $\mathcal{I}_1$ and $\mathcal{I}_2$ ; we simply need to know what the members of $\mathcal{I}_1$ and $\mathcal{I}_2$ look like locally (i.e. in $N(r) \cup \{r\}$ ).

We could go ahead and turn this into a fast algorithm now, but let’s wait and instead take some time to set-up some better notation.

Interlude on Structured decompositions

The tool we’ll need is called a structured decomposition, a general way of decomposing stuff into smaller constituent parts that Zoltan A. Kocsis, Jade Edenstar Master and I came up with. Roughly you should think of them as generalized graphs: rather than consisting of a set of vertices and an edge relation on this set, a structured decomposition is a collection of bags and a generalized relation on this collection. Here I’ll keep it simple, so I’ll avoid the general setting and I’ll only give the definition for graphs.

Fix the category $\mathbf{Gr}$ of graphs and graph homomorphisms. A structured decomposition of graphs (which I’ll simply refer to as a “decomposition” in this post) is any diagram in $\mathbf{Gr}$ that looks like this:

The idea is that you have some shape (a graph; in the example above it’s the tree with vertices w,x,y,z) to which you associate objects of the category $\mathbf{Gr}$ ; i.e. graphs. Each vertex of the shape is labeled with a graph; for example think of the graph $d(w)$ as the label of the vertex $w$ . Each edge of the shape is labeled by a span (a generalized relation) of graphs: for example the edge $e$ is labeled by the span $d(w) \xleftarrow{e_w} d(e) \xrightarrow{e_x} d(x)$ consisting of two graph homomorphisms $e_w: d(e) \to d(w)$ and $e_x: d(e) \to d(x)$ .

So where are we heading with these decompositions?

The point of the very informal definition I just gave, which was achieved by sweeping lots of details under the rug, is that you should think of a structured decomposition as a “recipe” for building graphs. If you come along and give me a structured decomposition $(H, d)$ of shape $H$ , then I can build a graph out of this recipie: for each edge $e= xy$ of $H$ , I glue the bag $d(x)$ to the bag $d(y)$ along the image of $d(e)$ . In other words I take a bunch of pushouts. Here’s an example of a graph (left hand side) built as a gluing (colimit) of a tree-shaped structured decomposition (right hand side):

A faster algorithm for Weighted Independent Set

Let’s use the syntax of structured decompositions to write down a faster algorithm for Weighted Independent Set.

First of all note that any tree $T$ can be obtained as a gluing of structured decomposition whose bags are two-vertex complete graphs; here’s an example.

So here’s the algorithm (sketch).

Suppose we are given a tree-shaped decompostion $(U, d)$ of the input tree $T$ . Pick any edge $(e = x_1x_2) \in E(U)$ . This edge partitions $U$ into two trees $U_1$ and $U_2$ (containing $x_1$ and $x_2$ respectively) and in so doing it also partitions $T$ into two trees: $T_1 = T|_{\bigcup_{u_1 \in U_1} d(u_1)}$ and $T_2 = T|_{\bigcup_{u_2 \in U_2} d(u_2)}$ .

Let $I_1$ be the set of all pairs $(\iota_1, n_1)$ where $\iota_1$ is an independent set in $d(x_1)$ and $n_1$ is the maximum weight of an independent set in $U_1$ whose intersection with $d(x)$ is $\iota_1$ . Let $I_2$ be defined similarly, but for $d(x_2)$ and $U_2$ .

Now we can compose and similarly to how we did before:
- for each $(\iota_1, n_1) \in I_1$ and $(\iota_2, n_2) \in I_2$ , conclude that there is an independent set of weight $n_1 + n_2 - w(\iota_1 \cap \iota_2)$ in $T$ whenever $\iota_1 +_{d(e)} \iota_2$ is an independent set in the graph $d(x) +_{d(e)} d(y)$ .

It’s not too hard to prove correctness, so I won’t do it here, but if you get stuck, have a look at any parameterized complexity book (for example Downey and Fellows Page 191).

The cool part is that this algorithm is much faster than the one I mentioned before. To see this, note that, since each bag of the decompostion always has at most two elements, the sets $I_1$ and $I_2$ have at most two elements (since there are at most two distinct independent sets on a connected graph with at most two vertices). Thus the entire algorithm requires time at most $4\mathcal{O}(|V(U)|) = 4\mathcal{O}(|V(T)|)$ .

That’s cool, but where is it heading?

It might seem a bit baroque of me to whip-out structured decompositions to solve such a this simple algorithmic problem on trees. But the point is that the algorithm above generalizes to other graph classes as well; in particular it generalizes to any graph class which has bounded tree-width. I’d love to tell you more about this, but it’ll have to wait for another post.

Until next time, a puzzle..

Earlier I noted that all trees can be built out of tree-shaped structured decompositions whose bags are either $K_1$ or $K_2$ . So here’s a quiz:

what graphs can be built out of tree-shaped structured decompositions whose bags are complete graphs?

Dirac found an answer in 1961, but I won’t tell you; I won’t spoil the fun.

One response to “Compositional Algorithms”

Compositional algorithms §2: quotienting solution spaces – Merlin's Notebook says:

16th November 2022 at 1:00 pm

[…] programming; specifically about solving Weighted Independent Set on trees. You can read about it here. Today things will get a bit more serious. I’ll start by briefly explaining how the algorithm […]

Loading…

Merlin's Notebook

Compositional Algorithms

Algorithms on recursive structure

Interlude on Structured decompositions

So where are we heading with these decompositions?

A faster algorithm for Weighted Independent Set

So here’s the algorithm (sketch).

That’s cool, but where is it heading?

Until next time, a puzzle..

Like this:

One response to “Compositional Algorithms”

Leave a ReplyCancel reply

Compositional Algorithms

Algorithms on recursive structure

Interlude on Structured decompositions

So where are we heading with these decompositions?

A faster algorithm for Weighted Independent Set

So here’s the algorithm (sketch).

That’s cool, but where is it heading?

Until next time, a puzzle..

Share this:

Like this:

One response to “Compositional Algorithms”

Leave a ReplyCancel reply