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

CREATORJessica Enright, Samuel D. Hand, Laura Larios-Jones, Kitty Meeks
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE232 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2505-15699

Browse the full library · About the Tower of Babel