Parameterised algorithms for temporally satisfying reconfiguration problems

Tom Davot, Jessica Enright, Laura Larios-Jones · 2025

Read Parameterised algorithms for temporally satisfying reconfiguration problems by Tom Davot, Jessica Enright, Laura Larios-Jones (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-2502-11961.txt.

Description

Tom Davot, Jessica Enright, and Laura Larios-Jones study in 2025 reconfiguration problems on graphs that change over time. A task such as picking an independent set on a static graph becomes, over time, a sequence of picks where tokens slide along edges that are active at each step. The question is whether one valid pick can be reshaped into another by such moves.

Checking whether a reshaping exists can be done efficiently, the team shows. Approximation results from the static problem also carry over, with a factor tied to the length of the time span. Their main algorithms are efficient when key traits are small, such as the time span or the width of the underlying graph.

Catalog record

CREATORTom Davot, Jessica Enright, Laura Larios-Jones
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE71 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2502-11961

Browse the full library · About the Tower of Babel