During Thanksgiving week I went to Wytham Abbey, a manor house in Oxfordshire where the “Workhop on Non-Compositionality in Complex Systems” was taking place. The workshop (organized by Matteo Cappucci and Jules Hedges) was centered around four papers that covered the theme of compositional patterns and emergence therein. I wrote one of them (the one on Structured Decompositions which I authored with Zoltan Kocsis and Jade Master) and you can find the other three here: 1, 2, 3. It was a truly lovely week of research in beautiful frescoed rooms warmed by fireplaces that Fabrizio would diligently keep burning at their maximum capacity.

While I was there, I worked with Fabrizio Genovese, Caterina Puca and Daniel Rosiak on some ideas that Daniel, James Fairbanks and I had been throwing around for a while, namely: “can you use cohomology to detect the failures of compositionality of a computational problem?” This ended up requiring us to spend a week computing in a frenzy, but the outcome amounted to many deep observations that we’re still trying to digest fully. The goal of this blog post is to just explain why I (really I should say “we“) think that cohomology is the right tool for making sense of emergence.

Computational Problems as Presheaves

I like to think of computational problems as presheaves assigning a set of solutions (i.e. a solution space) to each object \(c\) in some category of inputs. For example consider the “fruit fly” of computational complexity theory: the \(k-\texttt{VertexCover}\) problem. It is the decision problem that asks whether a given graph \(G\) contains a vertex subset \(S\) of size at most \(k\) (some given integer) such that the removal of \(S\) from \(G\) yields an edgeless graph. An example of a graph with a vertex cover of size two is shown below (pick \(\{b,d\}\) as the vertex cover).

You can encode this problem as a presheaf \(\mathcal{V}_k \colon \mathsf{Grph}^{op}_{mono} \to \mathsf{Set}\) which is a “functor by pullback” acting on objects as follows: $$\mathcal{V}_k \colon G \mapsto \{S \subseteq G \mid |S| \leq k \text{ and } G – S \text{ edgeless}\}.$$ (Note that you really need to start with the category of graphs and monomorphisms if you want this to actually be functorial since otherwise the size of the vertex covers might blow up when you pull them back along arbitrary morphisms.)

An Example: Solving Vertex Cover by Dynamic Programming on a Decomposed Graph.

Suppose we’re given a graph \(G\) and a cover of \(G\) (i.e. a structured decomposition) consisting of a collection \((U_i)_{i \in I}\) of subgraphs of \(G\) whose colimit is \(G\). Can we solve \(k-\texttt{VertexCover}\) on the instance \(G\) by only computing locally on the pieces \((U_i)_{i \in I}\) of the cover?

The answer is yes and you’ll see why in moment. But I’m not going to bother telling you the whole solution because it’s more complicated than it needs to be and it would obfuscate the point I’m trying to make. Instead, I’ll tell you an easier story: rather than considering any cover \((U_i)_{i \in I}\), we’ll only focus on path decompositions. Intuitively a path decomposition is a cover where each open \(U_i\) has non-empty intersections with \(U_{i-1}\) and \(U_{i+1}\) and empty intersection otherwise. More precisely, a path decomposition of a graph \(G\) is a diagram that looks like a sequence of monic spans whose colimit is \(G\). For example a path decomposition into \(n\) pieces \(U_1, U_2, \dots, U_n\) might look like $$U_1 \hookleftarrow U_{1, 2} \hookrightarrow U_2 \hookleftarrow U_{2,3} \hookrightarrow U_3 \dots U_{n-1} \hookleftarrow U_{n-1, n} \hookrightarrow U_n.$$

So how might we solve \(k-\texttt{VertexCover}\) by dynamic programming on a path decomposition?

To see how to do this, let’s start with an even easier presheaf, namely the one that takes a graph to all of its vertex covers without any size restrictions. Let’s call this \(\mathcal{V} \colon \mathsf{Grph}^{op}_{mono} \to \mathsf{Set}\). This presheaf is actually a sheaf, meaning that, if we are given a vertex cover \(S_i\) in \(U_i\), say and a vertex cover \(S_j\) in \(U_j\), then we can always construct a unique vertex cover \(S\) on the union (pushout) of \(U_i\) and \(U_j\) which restricts to \(S_i\) (resp. \(S_j\)) on \(U_i\) (resp. \(U_j\)) whenever \(S_i |_{U_i \cap U_j} = S_j |_{U_i \cap U_j}\) (i.e. whenever the two vertex covers agree over the intersection \(U_i \cap U_j\)).

The fact that \(\mathcal{V}\) is a sheaf has profound algorithmic consequences (which you can read about in my paper with Ernst Althaus, James Fairbanks and Daniel Rosiak) which let us design fast dynamic programming algorithms. In this concrete case the dynamic programming algorithm to decide if \(\mathcal{V}(G)\) is empty (i.e. \(G\) is a no-instance) or not goes as follows.

– You start with the given path decomposition $$U_1 \hookleftarrow U_{1, 2} \hookrightarrow U_2 \hookleftarrow U_{2,3} \hookrightarrow U_3$$ of the input graph \(G\) (for simplicity let’s assume we only have three opens).

– Then you apply \(\mathcal{V}\) to this decomposition to get the following diagram of sets: $$\mathcal{V}(U_1) \hookrightarrow \mathcal{V}(U_{1, 2}) \hookleftarrow \mathcal{V}(U_2) \hookrightarrow \mathcal{V}(U_{2,3}) \hookleftarrow \mathcal{V}(U_3)$$

which represents the local solution spaces \(\mathcal{V}(U_i)\) and their restriction maps to the pairwise intersections.

– Now we compute the pullback \(\mathcal{V}(U_1) \times_{\mathcal{V}(U_{1, 2})} \mathcal{V}(U_2)\) and we remove from \(\mathcal{V}(U_1)\) and \(\mathcal{V}(U_2)\) any element which is not in the range of the legs of the pullback cone.

– Finally repeat the previous step for \(\mathcal{V}(U_2)\) and \(\mathcal{V}(U_3)\) and answer “NO” if any of sets associated to \(U_1\), \(U_2\) or \(U_3\) after this process of filtering are empty.

Since \(\mathcal{V}\) is a sheaf, it’s not too hard to see that this algorithm is correct (for an actual statement of the algorithm I sketched above and its proof of correctness in a much more general case, see our paper). Furthermore this algorithm is fast since it takes time at most \(2^{2k} \cdot n\) where \(n\) is the number of pieces in the path decompsotion (in the example above we had \(n = 3\)).

At this point one might ask whether this same approach might work if we replace the presheaf \(\mathcal{V}\) with the one we actually care about, namely \(\mathcal{V}_k\). Unfortunately this doesn’t work and it fails because \(\mathcal{V}_k\) is not a sheaf. To see why, observe that, although we might have two vertex covers \(S_i\) and \(S_j\) of size at most \(k\) on some opens \(U_i\) and \(U_j\), even if we have that \(S_i |_{U_i \cap U_j} = S_j |_{U_i \cap U_j}\), we are not guaranteed that the union \(S_i +_{S_i |_{U_i \cap U_j}} S_j\) has size at most \(k\).

Now staring at this, one might get the feeling that this is the only way in which the \(k-\texttt{VertexCover}\) problem fails to be compositional, but how can we make this intuition precise?

Čech Cohomology for Vertex Cover

To study the failures of compositionality of the \(k-\texttt{VertexCover}\) problem, we’ll first need to set ourselves up for some cohomology. First of all, consider the nerve

of the path decomposition. We will use define the following augmented complex

where \(F\) to denotes the functor obtained by composing \(\mathcal{V}_k\) with the free Abelian group functor and where the coboundary maps are given by $$ \delta^{-1} \colon \bigl (s \in \mathcal{V}_k(G) \bigr) \mapsto \bigl (s|_{U_i})_{i \in I} \quad \text{ and } \quad \delta^n \colon s \mapsto \sum_{j = 0}^{n} (-1)^j F(d_{n,i})(s). $$

As usual we will define the \(n\)-th cohomology group \(H^n\) as the quotient \(H^n := \ker \delta^n / \text{im} \delta^{n-1}\). Now notice that, if \(F\) were a sheaf, then \(H^0\) as defined with respect to this augmented complex would be trivial. To see this, observe that \(\ker \delta^0\) is generated exactly by the matching families of the sheaf and thus, if \(F\) were a sheaf, then each matching family would lift to a unique global section (i.e. each matching family would be in the image of \(\delta^{-1}\)). For a presheaf which refuses to be a sheaf (such as our \(F\) as we just defined it above), however, \(H^0\) is generated exactly by those families of local vertex covers, which, despite being in pairwise agreement, fail to lift to global solutions.

This is wonderful: what we just did was deduce that the obstructions to compositionality are given by the generators of \(H^0\). But what does this mean concretely? And does this agree with our intuition that the only way in which \(\mathcal{V}_k\) fails to be compositional is that local vertex covers may glue into vertex covers that are too large (i.e. they exceed our budget of \(k\) vertices)?

It’s time to compute!

Let’s make this a small example. Take \(k = 2\) and let \(G\) be a four-cycle with vertices \(a,b,c,d\) and let’s consider a path decomposition of \(G\) into two parts \(U_1\) and \(U_2\) where \(U_1\) is the two-edge path \(d-a-b\) and \(U_2\) is the two-edge path \(d-c-b\). Now enumerate the local vertex covers of size at most \(2\); these are (below I’m dropping parentheses, so read \(a\) as \(\{a\}\) and \(ab\) as \(\{a,b\}\) etc.):

$$\mathcal{V_2}(U_1) = \{a, ab, ad, bd\} \quad \text{ and } \quad \mathcal{V_2}(U_2) = \{c, bc, dc, bd\}.$$

Since \(U_{12}\) consists solely of the vertices \(b\) and \(d\) (and no edges), we have that \(\mathcal{V}_2(U_{12}) = \{\emptyset, b, d\}\) and hence the matching familes are

$$\ker \delta^0 = \{(a, c), (ab, bc), (ad, dc), (bd, bd)\}$$

while, since \(\mathcal{V}_2(G) = \{ac, bd\}\), we have

$$\text{im} \delta^{-1} = \{(a,c), (bd, bd)\}.$$

Thus we have that \(H^0\) has two generators (namely these are \((ab, bc)\) and \((ad, dc)\)) which correspond precisely to those local vertex covers which agree on the intersection, but whose union is too large!

Does this work this nicely for other problems?

The answer is a resounding yes! If you want to try it out, I suggest you try the \(k-\texttt{CycleTransversal}\) problem which asks to find a set \(S\) of vertices whose removal from the host graph \(G\) renders it a forest. This too can be cast as a presheaf by pullback and this too refuses to be a sheaf. The interesting thing is that, if you try to compute \(H^0\) for this presheaf on the same graph and cover described in the previous example, you’ll end up with three generators: two of them will describe issues relating to the size of the glued solutions (just like in the case of vertex cover) but the third one is different, it describes the fact that two local cycle covers can agree, but their gluing can fail to cover all the global cycles!

Looking ahead

Ideally it would be wonderful if we could make use of the information of \(H^0\) to automatically come up with dynamic programming algorithms. I have many ideas of how to do this and, based on my ongoing work with Spencer Breiner, Matteo Cappucci, James Fairbanks and Daniel Rosiak, I think these are all very promising. However, for now it’s unclear whether we can actually turn this cohomological information into a practical tool for designing combinatorial algorithms. On the bus ride from Wytham Abbey to Heathrow airport, I was told that cohomology groups are sheaves. If that’s true, then I have some good news for us all… but I’m having a hard time hunting down the precise result. If anyone knows about this, please reach out, I’d love to know the details!

Until next time,

Ben