4 citations · 9 across the 15 of their papers we have counts for
17 papers
Time-Varying Data as Sheaves: an Invitation to Narratives
Wilmer Leal, Benjamin Merlin Bumpus, Jana K. Nickel +3
Modern science and engineering increasingly rely on time-varying data, yet the mathematical tools used to model temporal phenomena are often developed within separate disciplines,…
Decomposing time-varying data into simple pieces: structured decompositions of narratives
Benjamin Merlin Bumpus, Jana K. Nickel
Graphs that change over time arise throughout applications, but there is no single standard way to decompose them into smaller pieces. In this paper, we propose a systematic catego…
: Truly Linear FPT
Benjamin Merlin Bumpus, Rod Downey, Tala Eagling-Vose +7
Parameterized complexity has always been concerned with practical computing: by confining combinatorial explosion to a secondary parameter , one can uncover why and how many NP-…
A Parameterized Algorithm for Testing whether the Limit of a Diagram is Empty
Ernst Althaus, Benjamin Merlin Bumpus, James Fairbanks +2
A limit of a (small) diagram in a complete category can be thought of as specifying a set of equations involving the objects of . To motivate this intuitively,…
Lassos: Pushing Tree Decompositions Forward Along Homomorphisms
Benjamin Merlin Bumpus, James Fairbanks, Will J. 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,…
Algorithmic and Extremal Obstructions Through the Language of Cohomology
Anny Beatriz Azevedo, Benjamin Merlin Bumpus, Matteo Capucci +2
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 solu…
Towards a Unified Theory of Time-Varying Data
Benjamin Merlin Bumpus, James Fairbanks, Martti Karvonen +2
What is a time-varying graph, a time-varying topological space, or, more generally, a mathematical structure that evolves over time? In this work, we lay the foundations for a gene…
Additive Invariants of Open Petri Nets
Benjamin Merlin Bumpus, Sophie Libkind, Jordy Lopez Garcia +2
We classify all additive invariants of open Petri nets: these are -valued invariants which are additive with respect to sequential and parallel composition of open Petr…
Compositional Algorithms on Compositional Data: Deciding Sheaves on Presheaves
Ernst Althaus, Benjamin Merlin Bumpus, James Fairbanks +1
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 initia…
Structured Decompositions: Structural and Algorithmic Compositionality
Benjamin Merlin Bumpus, Zoltan A. Kocsis, Jade Edenstar Master +1
We introduce structured decompositions, category-theoretic structures which simultaneously generalize notions from graph theory (including treewidth, layered treewidth, co-treewidt…
Search-Space Reduction via Essential Vertices
Benjamin Merlin Bumpus, Bart M. P. Jansen, Jari J. H. 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…
Degree of Satisfiability in Heyting Algebras
Benjamin Merlin Bumpus, Zoltan A. Kocsis
Given a finite structure and property , it is a natural to study the degree of satisfiability of in ; i.e. to ask: what is the probability that uniformly randomly cho…
Treewidth via Spined Categories (extended abstract)
Zoltan A. Kocsis, Benjamin Merlin Bumpus
Treewidth is a well-known graph invariant with multiple interesting applications in combinatorics. On the practical side, many NP-complete problems are polynomial-time (sometimes e…
Spined categories: generalizing tree-width beyond graphs
Benjamin Merlin Bumpus, Zoltan A. Kocsis
Tree-width is an invaluable tool for computational problems on graphs. But often one would like to compute on other kinds of objects (e.g. decorated graphs or even algebraic struct…
Edge exploration of temporal graphs
Benjamin Merlin Bumpus, Kitty 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 tempora…
Directed branch-width: A directed analogue of tree-width
Benjamin Merlin Bumpus, Kitty Meeks, William Pettersson
Gurski and Wanke showed that a graph class C has bounded tree-width if and only if its associated class of directed line graphs has bounded clique-width. Inevitably -- asking wheth…
A Constraint Model for the Tree Decomposition of a Graph
Benjamin Bumpus, Patrick Prosser, James Trimble
We present a constraint model for the problem of producing a tree decomposition of a graph. The inputs to the model are a simple graph G, the number of nodes in the desired tree de…