# BENJAMIN MERLIN BUMPUS

I do research at the nexus of mathematics and computer science in the Formal Analysis, Theory and Algorithms group under the supervision of Kitty Meeks . I study graph decompositions and graph connectivity in the context of parameterized algorithms. I am particularly interested in building a theory of decompositions for more general classes of objects than just finite simple graphs. My research involves a blend of graph theory and category theory.

Non-technical research summary: I am interested in finding ways of "splitting up" (decomposing) large objects into small parts in an algorithmically useful way. The idea is that, given some hard computational problem, we solve the problem on the parts and then deduce an answer on the whole.

I am finishing my PhD in 2021 and I am looking for Postdoctoral opportunities across Europe in the following areas:

-- graph theory (including digraphs, temporal graphs and infinite graphs)

-- parameterized complexity

-- graph decompositions

-- graph containment relations

-- graph homomorphisms

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

## RESEARCH

Here are my Orchid ID and my ResearchGate profile.

### PUBBLICATIONS AND PRE-PRINTS

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.

Spined categories: generalizing tree-width beyond graphs. [Bumpus, Kocsis] 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

Dagstuhl Seminar on 'Temporal Graphs: Structure, Algorithms, Applications' (invited, upcoming 25. – 30. April)

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

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

Karlsruhe IT: discrete math seminar (invited)

2019

2018

British Combinatorics Conference

Oxford one day meeting in Combinatorics

British Combinatorial Colloquium

### CONFERENCES THAT I ORGANIZED

2020

I am 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. Sign up for the mailing list here. For any questions, email me or contact one of the other organizers: Michael McKay and Jake Horsfield.

I am the lead organizer of PCC2020: the Postgraduate Combinatorics Conference. Unfortunately this is 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

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

## OUTREACH

### 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

September 2017 - May 2021

### PHD CANDIDATE

I am a PhD candidate in the School of Computing Science at the University of Glasgow. Here I am part of the "Formal Analysis, Theory and Algorithms" research group. It's a vibrant and active group which you (yes you!) should visit!

September 2013 - June 2017

### B.SC. (HONOURS) MATHEMATICS AND ITS APPLICATIONS, FIRST-CLASS

I was awarded the Prize for An outstanding Performance in the Final Year of a Mathematics Degree. In Stirling I worked as a summer research intern with Anthony O'Hare, Jessica Enright and Adam Kleczkowski. They are all lovely people who do lots of intersting work, so I encourage you to seek them out if you are interested in their research!

September 2008 - June 2013

### ISTITUTO TECNICO AGRARIO "G. PASTORI" (HIGH SCHOOL)

Upon graduating I became a certified "Perito Agrario" ("Agronomist" in English).

## BIO

I am half Italian and half US-American. I was born and raised in Italy (except for half a decade or so during which I lived in Florida) and I moved to Scotland to pursue higher education.

Given my current area of work, many would be surprized to know that I am a certified "Perito Agrario" ("Agronomist" in English). This of course means that I have a passion for agriculture and related topics.

If I'm not in my office, you can probably find me in the Botanic Gardens! Although you should probably try peering through the many plants around my desk to make sure I'm really not there before you seek me out elsewhere. If you're looking for more conversation topics, try one of these:

I love rock-climbing and bouldering,

I play the guitar and the mandolin.

## GET IN TOUCH

Mailing Address:

Sir Alwyn Williams Building

University of Glasgow

Glasgow G12 8RZ

SCOTLAND

United Kingdom

Visiting address:

Room G161

Sir Alwyn Williams Building

Glasgow G12 8RZ

Scotland