9 papers
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,…
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 sol…
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…
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,…