BENJAMIN MERLIN BUMPUS

I am a postdoc at the Eindhoven University of Technology, working with Bart Jansen.

Before that, I did a PhD at the University of Glasgow in the Formal Analysis, Theory and Algorithms group under the supervision of Kitty Meeks.

​

I do research at the nexus of mathematics and computer science.

My reseach focuses on complexity theory and it often involves a blend of techniques from the following areas: (1) graph theory, (2) parameterized complexity and (3) category theory. Feel free to get in touch if you want to chat about any of these topics.

​

What is complexity theory?

Avoiding the technical answer, let's stick with the intuitive one: more often than not, the best provably-correct algorithms that we know of are prohibitively slow. But what do I mean by 'slow'? Well, suppose for example that we have an algorithm (presumably one that answers some question which is very important to us) whose running time depends exponentially – say proportionally to 2n – on the input size n. Suppose we can process n data points in a minute, if, after a few more days of data-collection, we collect another 20 data points, our algorithm now takes over a year to run. This algorithm is clearly too 'slow' for practical use. The fact that the best provably-correct algorithms that we know of are 'slow' is clearly a problem.

​

What do I do within complexity theory?

Rather than trying to find an algorithm that is 'fast' for any input, I take a taxonomical approach: I study classes of inputs and exploit their structural properties to obtain fast algorithms.

​

What excites me the most is understanding exactly why certain types of structure can be exploted algoithmically. Often this means that I try generalize our current techniques to gain a deep understanding of why they work and of how far they can be pushed.

​

​

​

​

List of keywords: spined categories, tree-width, branch-width, rank-width, clique-width, modular decompositions (directed variants of all of these as well), directed graphs, temporal graphs, connectivity, graph minors, graph immersions, vertex minors, lattices.

PUBBLICATIONS AND PRE-PRINTS

​

• Structured Decompositions: Structural and Algorithmic Compositionality [Bumpus, Kocsis, Master] 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; to appear at the European Symposium on Algorithms] 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.

• 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] (BEST PAPER AWARD at IWOCA 2021) 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. (Here is a recording of a talk I gave on this topic for the 'Dagstuhl Seminar on temporal graphs'.)

• Spined categories: generalizing tree-width beyond graphs. [Bumpus, Kocsis; watch a talk recording --> click 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] (submitted) 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.

​

Past Research Experience: 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.

TALKS

2021

• ACPMS Algebraic and Combinatorial perspectives in the mathematical sciences (invited, upcoming: Dec. 3rd 2021)

• University of Glasgow - Formal Analysis, Theory & Algorithms (invited, upcoming: Nov. 23rd 2021)

• TU Ilmenau combinatorics seminar - Fachgebiet Large Networks and Random Graphs (invited, upcoming: Nov. 4th 2021)

• Graphes en Rhône Alpes Auvergne (Grenoble and Clermont-Ferrand joint seminar on graph theory and algorithms) (invited)

• Category Theory CT20->21 conference; you can watch the video recording here.

• IWOCA 2021: 32nd International Workshop on Combinatorial Algorithms (best paper award)

• British Combinatorial Conference 2021

• TU Berlin: Algorithmik und Komplexitätstheorie research group (invited)

• Dagstuhl Seminar on 'Temporal Graphs: Structure, Algorithms, Applications' (invited,  25. – 30. April) A recording of this talk is available on YouTube; you can find it here.

• IBS Discrete Mathematics Group (DIMAG), Daejeon, South Korea: Virtual Discrete Math Colloquium (invited)

• British Colloquium on Theoretical Computer Science (link to schedule here) 2021

• University of Birmingham: Study group in Graph Theory, Topology and Algorithms (invited)

• TU Berlin: Logic and Semantics Research Group (invited)

• Karlsruhe IT: discrete math seminar (invited)

2020 - Alea iacta est

• Karlsruhe IT: discrete math seminar (invited)

2019

• British Colloquium on Theoretical Computer Science & AlgoUK

• Scottish Combinatorics Meeting

• Postgraduate Combinatorial Conference

• British Combinatorial Conference

​

2018

• Postgraduate Combinatorics Conference

• AlgoUK

• British Combinatorics Conference

• Oxford one day meeting in Combinatorics

• Scottish Combinatorics Meeting

• British Combinatorial Colloquium

CONFERENCES THAT I ORGANIZED

​

2020

• I was the founder and lead organizer of the e-PCC. This is an online seminar series for PhD students across Europe in discrete mathematics and/or theoretical computer science.

• I was the lead organizer of PCC2020: the Postgraduate Combinatorics Conference. Unfortunately this was postponed due to COVID19

​

2016

• Stirling Graph Theory Spring School. Invited speakers: Jessica Enright, Kitty Meeks, John Faben.

​

SUMMER SCHOOLS AND READING GROUPS

Organised

• Course Coordinator for the Programming Workshop for Scientists in Africa 2017-2019

• Stirling Graph Theory Spring School. Invited speakers: Jessica Enright, Kitty Meeks, John Faben.

​

Attended

• An Excursion into Model Theory and its Applications

• Recent Advances in Parameterized Complexity

​

Reading Groups

• (Parameterized) Algorithms and Discrete Mathematics reading group within the Formal Analysis, Theory and Algorithms group in Glasgow

• Undergraduate Reading group: "Totally QE'D" together with Pernille Rytterhuus and Zoltan A. Kocsis

AWARDS

• 3.5 years EPSRC Doctoral Research Scholarship, University of Glasgow (value: £ 111,000)
  

• Best in Europe (i.e. top 4% worldwide) in the MCM mathematical modelling competition

• Prize for An outstanding Performance in the Final Year of a Mathematics Degree

PWSAFRICA

I was part of organizing and tutoring team of Programming Workshop for Scientists in Africa.  The team memebers I worked with are: Sofiat Olaosebikan (the project founder) Tom Wallis, Fionnuala Johnson, Fatma Elsafoury, Ifeoma Okoh, Paul John and Alexandrina Pancheva.

• In 2019 I was the course coordinator for our course in Kigali, Rwanda. I developed the curriculum for the two-week long Python programming workshop. The workshop was delivered in a “Project-Based Learning” style inspired by textbooks such as Lovász’s “Combinatorial Problems and Exercises”. The workshop was a huge success with students who had never programmed before being able to understand and write a small language interpreter within only two weeks. (The credit should go to the students, though!). You can find the course materials HERE.

• In 2018 we went to Ibadan, Nigeria. If you are interested in reading more about this experience, then you should read the article I wrote for the March 2019 edition of the London Mathematical Society Newsletter!

TUTOR FOR PROJECT GRASP

Project Grasp is an initiative targeting students from local Glasgow high schools, organised at the University of Glasgow by Adam Kurkiewicz, Jordan Baillie and Samko Gurský in partnership with Skyscanner.

UNIVERSITY OF GLASGOW

Supervision:

• Rory Barnett. Undergraduate Dissertation on "Finding k-blocks in practice". A k-block describes a highly connected vertex-set in a graph. Rory implemented an algorithm described in a paper by Carmesin, Diestel, Hamman and Hudtermark which finds all k-blocks in a graph (either for all k or for fixed k).

​

Tutor:

• ALGORITHMS & DATA STRUCTURES 2

• ALGORITHMS AND DATA STRUCTURES (Masters level)

EDUCATION