Compositional Algorithms with Sheaves

A general theory of data that changes over time, built as sheaves on posets of time intervals – categories of narratives. It defines both temporal objects and their morphisms, distinguishes cumulative from persistent readings and moves between them, lifts static notions to temporal ones systematically, works for any category with limits and colimits, and connects to dynamical systems. Time-varying graphs have been reinvented repeatedly with incompatible definitions. This is the lab’s answer to what all of them are instances of, and the sheaf-theoretic machinery is the same as the rest of the project.

Read it for The five desiderata in the introduction, then the definition of a narrative. The comparisons to existing temporal graph formalisms can be sampled.

A problem becomes a presheaf assigning certificates to instances, and Cech cohomology of that presheaf measures exactly how local solutions fail to patch into global ones. Applied to Vertex Cover, Cycle Cover and Odd Cycle Transversal, the obstructions show up as concrete phenomena – hidden cycles, local solutions that inflate – and classical results such as Koenig’s theorem are recovered in cohomological terms. The compositional algorithms only work when local answers glue. This is the project’s account of what is happening when they do not, which is the more common case.

Read it for The cohomological reading of Koenig’s theorem, which is where the machinery first pays for itself.

Read first Compositional Algorithms on Compositional Data: Deciding Sheaves on Presheaves

Treewidth is monotone under subgraphs and contractions; the paper shows that contractions are, up to isomorphism, the only surjective graph homomorphisms that preserve tree decompositions and the shape of the decomposition tree. It proves this by introducing the lasso, which is what a contraction becomes in an arbitrary category with pushouts of monomorphisms, so that the same question can be asked of directed multigraphs, hypergraphs, Petri nets, databases, simplicial sets and the rest. Decompositions are the lab’s tool for turning a hard global problem into local ones, and this settles which maps between structures a decomposition can be carried along.

Read it for The characterization theorem, then the lasso, which the authors flag as of independent interest and which is what carries the result beyond graphs.

A way to ask how badly a functor fails to be compositional, and what can be done about it. The paper introduces lavish presheaves – presheaves satisfying the existence half of the sheaf condition but not uniqueness – as the setting in which such failures can be measured rather than merely observed. Compositionality is usually presented as a property a construction either has or lacks. The sheaves project needs it to be a quantity, because the interesting structures are the ones that almost have it.

Read it for The definition of a lavish presheaf and the two squares of the title.

The folklore that dynamic programming is the right approach on compositionally structured graphs, made general and made precise. Structured decompositions define Grothendieck topologies on adhesive categories of data, and any problem expressible as a sheaf for one of those topologies can be decided in linear time on inputs of bounded decomposition width whose decomposition shapes have bounded feedback vertex number. This is the theorem the sheaves project is organized around: it says which problems the compositional algorithms apply to, and it applies to any C-set category, so the same statement covers graphs, hypergraphs, databases and simplicial complexes at once.

Read it for The topology construction and the main theorem. The catalogue of structures it specializes to is worth a skim to see how wide the result is.