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 of some input vertex-weighted tree which has maximum weight such that that no two vertices of are adjacent in .
The compositional structure of trees comes in handy: trees can be built from smaller trees by glueing along shared copies of (the 1-vertex complete graph; I’ll abbreviate it simply as ““). In category theory this is called a pushout; I’ll adopt this notation here: pick two vertices of two trees and — by choosing homomorphisms — then the pushout of this diagram is the tree obtained by “gluing” the image of in to its image in .
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 along some “root’ vertex and suppose further that we already computed all of the independent sets in and — let’s call these and –, then we observe that we can compute all of the independent sets in by matching-up the independent sets of with those of . Explicitly, given any two independent sets and in and , they can be combined into an independent set for iff is an independent set in the closed neighborhood of (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 and , we only needed to check that their union gave us an independent set locally (i.e. on the closed neighborhood of ) 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 and ; we simply need to know what the members of and look like locally (i.e. in ).
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 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 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 ; i.e. graphs. Each vertex of the shape is labeled with a graph; for example think of the graph as the label of the vertex . Each edge of the shape is labeled by a span (a generalized relation) of graphs: for example the edge is labeled by the span consisting of two graph homomorphisms and .
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 of shape , then I can build a graph out of this recipie: for each edge of , I glue the bag to the bag along the image of . 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 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 of the input tree . Pick any edge . This edge partitions into two trees and (containing and respectively) and in so doing it also partitions into two trees: and .
- Let be the set of all pairs where is an independent set in and is the maximum weight of an independent set in whose intersection with is . Let be defined similarly, but for and .
- Now we can compose and similarly to how we did before:
- for each and , conclude that there is an independent set of weight in whenever is an independent set in the graph .
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 and 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 .
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 or . 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.