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
.
- for each
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.
One response to “Compositional Algorithms”
[…] 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 […]