Families of tractable problems with respect to vertex-interval-membership width and its generalisations
Jessica Enright, Samuel D. Hand, Laura Larios-Jones, Kitty Meeks · 2025
Read Families of tractable problems with respect to vertex-interval-membership width and its generalisations by Jessica Enright, Samuel D. Hand, Laura Larios-Jones, Kitty Meeks (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2505-15699.txt.
Introduction
Jessica Enright, Samuel Hand, Laura Larios-Jones, and Kitty Meeks advanced the theory of temporal graphs in twenty twenty-five. In temporal graphs, edges exist only at set times, which models real networks but makes many problems harder than in static graphs. Width parameters tame that hardness by bounding how many vertices must be tracked at once.
The authors introduce tree-interval-membership width, a new parameter that generalizes several earlier ones. They then give meta-algorithms that work for whole families of problems at once under both the new and the older parameter. This yields a clean characterization of which problems become tractable. Applications include time-respecting Hamiltonian paths, dominating sets, matchings, and edge deletion to limit reach. The work replaces many case-by-case proofs with one reusable engine.
Catalog record
| CREATOR | Jessica Enright, Samuel D. Hand, Laura Larios-Jones, Kitty Meeks |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 232 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2505-15699