You can read my PHD thesis here and these are my Orchid ID and my ResearchGate profile.
Pushing Tree Decompositions Forward Along Graph Homomorphisms
[Bumpus, Fairbanks, Turner]
It is folklore that tree-width is monotone under taking subgraphs (i.e. injective graph homomorphisms) and contractions (certain kinds of surjective graph homomorphisms). However, although tree-width is obviously not monotone under any surjective graph homomorphism, it is not clear whether contractions are canonically the only class of surjections with respect to which it is monotone. We prove that this is indeed the case: we show that – up to isomorphism – contractions are the only surjective graph homomorphisms that preserve tree decompositions and the shape of the decomposition tree. Furthermore, our results provide a framework for answering questions of this sort for many other kinds of combinatorial data structures (such as directed multigraphs, hypergraphs, Petri nets, circular port graphs, half-edge graphs, databases, simplicial complexes etc.) for which natural analogues of tree decompositions can be defined.
Algorithmic and Extremal Obstructions Through the Language of Cohomology
[Azevedo, Bumpus, Capucci, Fairbanks, Rosiak]
(My student Anny Beatriz Azevedo gave a short talk about this, you can watch it here).
We model problems as presheaves that assign sets of certificates to input instances, and we show how to use presheaf Čech cohomology to capture the precise ways in which local solutions fail to patch into global ones. Applied to problems like Vertex Cover, Cycle Cover, and Odd Cycle Transversal, our framework exposes emergent phenomena such as hidden cycles or the inflation of small, local solutions. This approach not only rephrases classical results like König’s Theorem in cohomological terms, but also reveals how to systematically account for failures of compositionality. Although our main focus is on presheaves of sets, the methods generalize naturally to Abelian presheaves, suggesting a rich interplay between graph theory, cohomology, and complexity. This work represents a first step toward a systematic, sheaf-theoretic theory of algorithmic structure and related obstructions.
[Bumpus, Jansen, Venne] SWAT2024
For a positive real γ ≥ 1, a γ-certified algorithm for a vertex-weighted graph optimization problem is an algorithm that, given a weighted graph (G,w), outputs a re-weighting of the graph obtained by scaling each weight individually with a factor between 1 and γ, along with a solution which is optimal for the perturbed weight function. Here we provide (1+ε)-certified algorithms for Dominating Set and H-Subgraph-Free-Deletion which, for any ε > 0, run in time f(1/ε)⋅n^𝒪(1) on minor-closed classes of graphs of bounded local tree-width with polynomially-bounded weights. We obtain our algorithms as corollaries of a more general result establishing FPT-time certified algorithms for problems admitting, at an intuitive level, certain “local solution-improvement properties”. These results improve – in terms of generality, running time and parameter dependence – on Angelidakis, Awasthi, Blum, Chatziafratis and Dan’s XP-time (1+ε)-certified algorithm for Independent Set on planar graphs (ESA2019). Furthermore, our methods are also conceptually simpler: our algorithm is based on elementary local re-optimizations inspired by Baker’s technique, as opposed to the heavy machinery of the Sherali-Adams hierarchy required in previous work.
Towards a Unified Theory of Time-varying Data
[Bumpus, Fairbanks, Karvonen, Leal, Simard]
What is a time-varying graph, or a time-varying topological space and more generally what does it mean for a mathematical structure to vary over time? Here we introduce categories of narratives: powerful tools for studying temporal graphs and other time-varying data structures. Narratives are sheaves on posets of intervals of time which specify snapshots of a temporal object as well as relationships between snapshots over the course of any given interval of time. This approach offers two significant advantages. First, when restricted to the base category of graphs, the theory is consistent with the well-established theory of temporal graphs, enabling the reproduction of results in this field. Second, the theory is general enough to extend results to a wide range of categories used in data analysis, such as groups, topological spaces, databases, Petri nets, simplicial complexes and many more. The approach overcomes the challenge of relating narratives of different types to each other and preserves the structure over time in a compositional sense.
Furthermore our approach allows for the systematic relation of different kinds of narratives. In summary, this theory provides a consistent and general framework for analyzing dynamic systems, offering an essential tool for mathematicians and data scientists alike.
Additive Invariants of Open Petri Nets (in Compositionality)
[Bumpus, Libkind, Lopez Garcia, Sorkatti, Tenka]
We classify all additive invariants of open Petri nets: these are invariants valued in the natural numbers which are additive with respect to sequential and parallel composition of open Petri nets. In particular, we prove two classification theorems: one for open Petri nets and one for monically open Petri nets (i.e. open Petri nets whose interfaces are specified by monic maps). Our results can be summarized as follows. The additive invariants of open Petri nets are completely determined by their values on a particular class of single-transition Petri nets. However, for monically open Petri nets, the additive invariants are determined by their values on transitionless Petri nets and all single-transition Petri nets. Our results confirm a conjecture of John Baez (stated during the AMS’ 2022 Mathematical Research Communities workshop).
Compositional Algorithms on Compositional Data:
Deciding Sheaves on Presheaves[Althaus, Bumpus, Fairbanks, Rosiak]
Algorithmicists are well-aware that fast dynamic programming algorithms are very often the correct choice when computing on compositional (or even recursive) graphs. Here we initiate the study of how to generalize this folklore intuition to mathematical structures writ large. We achieve this horizontal generality by adopting a categorial perspective which allows us to show that: (1) structured decompositions (a recent, abstract generalization of many graph decompositions) define Grothendieck topologies on categories of data (adhesive categories) and that (2) any computational problem which can be represented as a sheaf with respect to these topologies can be decided in linear time on classes of inputs which admit decompositions of bounded width and whose decomposition shapes have bounded feedback vertex number. This immediately leads to algorithms on objects of any C-set category; these include — to name but a few examples — structures such as: symmetric graphs, directed graphs, directed multigraphs, hypergraphs, directed hypergraphs, databases, simplicial complexes, circular port graphs and half-edge graphs.
Thus we initiate the bridging of tools from sheaf theory, structural graph theory and parameterized complexity theory; we believe this to be a very fruitful approach for a general, algebraic theory of dynamic programming algorithms. Finally we pair our theoretical results with concrete implementations of our main algorithmic contribution in the AlgebraicJulia ecosystem.
Structured Decompositions: Structural and Algorithmic Compositionality
[Bumpus, Kocsis, Master, Minichiello]
We introduce structured decompositions: category-theoretic generalizations of many combinatorial invariants — including tree-width, layered tree-width, co-tree-width and graph decomposition width — which have played a central role in the study of structural and algorithmic compositionality in both graph theory and parameterized complexity. Structured decompositions allow us to generalize combinatorial invariants to new settings (for example decompositions of matroids) in which they describe algorithmically useful structural compositionality. As an application of our theory we prove an algorithmic meta theorem for the Sub_P-composition problem which, when instantiated in the category of graphs, yields compositional algorithms for NP-hard problems such as: Maximum Bipartite Subgraph, Maximum Planar Subgraph and Longest Path.
Search space reduction via essential vertices
[Bumpus, Jansen, de Kroon]
We investigate preprocessing for vertex-subset problems on graphs. While the notion of kernelization, originating in parameterized complexity theory, is a formalization of provably effective preprocessing aimed at reducing the total instance size, our focus is on finding a non-empty vertex set that belongs to an optimal solution. This decreases the size of the remaining part of the solution which still has to be found, and therefore shrinks the search space of fixed-parameter tractable algorithms for parameterizations based on the solution size. We introduce the notion of a c-essential vertex as one that is contained in all c-approximate solutions. For several classic combinatorial problems such as Odd Cycle Transversal and Directed Feedback Vertex Set, we show that under mild conditions a polynomial-time preprocessing algorithm can find a subset of an optimal solution that contains all 2-essential vertices, by exploiting packing/covering duality. This leads to FPT algorithms to solve these problems where the exponential term in the running time depends only on the number of non-essential vertices in the solution.
Conference version: European Symposium on Algorithms
Degree of Satisfiability in Heyting Algebras
[Bumpus, Kocsis]
Given some finite structure M and property p, it is a natural to study the
degree of satisfiability of p in M; i.e. to ask: what is probability that uniformly randomly chosen elements in M satisfy p? In group theory, a well-known result of Gustafson states that the equation xy = yx has a finite satisfiability gap: its degree of satisfiability is either 1 (in Abelian groups) or no larger than 5/8 . Degree of satisfiability has proven useful in the study of (finite and infinite) group-like and ring-like algebraic structures, but finite satisfiability gap questions have not been considered in lattice-like, order-theoretic settings yet. Here we investigate degree of satisfiability questions in the context of Heyting algebras and intuitionistic logic. We classify all equations in one free variable with respect to finite satisfiability gap, and determine which common principles of classical logic in multiple free variables have finite satisfiability gap. In particular we prove that, in a finite non-Boolean Heyting algebra, the probability that a randomly chosen element satisfies x ∨¬x = T is no larger than 2/3 . Finally, we generalize our results to infinite Heyting algebras, and present their applications to point-set topology, black-box algebras, and the philosophy of logic.
Edge exploration of temporal graphs.
[Bumpus, Meeks]
We introduce a natural temporal analogue of Eulerian circuits and prove that, in contrast with the static case, it is NP-hard to determine whether a given temporal graph is temporally Eulerian even if strong restrictions are placed on the structure of the underlying graph and each edge is active at only three times. However, we do obtain an FPT-algorithm with respect to a new parameter called interval-membership-width which restricts the times assigned to different edges; we believe that this parameter will be of independent interest for other temporal graph problems. Our techniques also allow us to resolve two open question of Akrida, Mertzios and Spirakis [CIAC 2019] concerning a related problem of exploring temporal stars.
(Best paper award at IWOCA 2021. Journal version in Algorithmica)
Talk recording here (from the ‘Dagstuhl Seminar on temporal graphs’).
Spined categories: generalizing tree-width beyond graphs.
[Bumpus, Kocsis] European Journal of Combinatorics (EJC) version. Talk recording here.
Problems that are NP-hard in general are often tractable on inputs that have a recursive structure. For instance consider classes defined in terms of `graph decompositions’ such as of bounded tree- or clique-width graphs. Given the algorithmic success of graph decompositions, it is natural to seek analogues of these notions in other settings. What should a `tree-width-k’ digraph or lattice or temporal graph even look like? Since most decomposition notions are defined in terms of the internal structure of the decomposed object, generalizing a given notion of decomposition to a larger class of objects tends to be an arduous task. Here we show how this difficulty can be reduced significantly by finding a characteristic property formulated purely in terms of the category that the decomposed objects inhabit, which defines the decomposition independently of the internal structure. We introduce an abstract characterisation of tree-width (called the triangulation functor) as a vast generalisation of Halin’s definition of tree-width as the maximal graph parameter sharing certain properties with the Hadwiger number and chromatic number. Our uniform construction of tree-width provides a roadmap to the discovery of new tree-width-like parameters simply by collecting the relevant objects into our new notion of a spined category. (You can also find a 3-page extended abstract related to this work here.)
Directed branch-width: A directed analogue of tree-width
[Bumpus, Meeks, Pettersson]
We introduce a new digraph width measure called directed branch-width. To do this, we generalize a characterization of graph classes of bounded tree-width in terms of their line graphs to digraphs. We show that problems such as directed Hamilton path and Max-Cut (which are hard when parameterized by other known directed width measures) are in FPT when parameterized by directed branch-width. More generally, we obtain an algorithmic meta-theorem for the model-checking problem for a restricted variant of MSO2-logic on classes of bounded directed branch-width.
In a past life
During my undergraduate degree at the University of Stirling, I undertook multiple posts as a research intern. These projects all had industrial and policy applications within the field of mathematical modeling for biology using techniques from evolutionary computing and metaheuristics under the supervision of: Anthony O’Hare, Jessica Enright and Adam Kleczkowski.