2024/06/18 by Nicolás Bousquet, Kshitij Gajjar, Bousquet, Nicolas +5
Computer Science · #Combinatorics (math.CO) #Computational Complexity (cs.CC) #Data Structures and Algorithms (cs.DS) #Embedded Systems Design Techniques #FOS: Computer and information sciences #FOS: Mathematics #Graph Theory and Algorithms #Interconnection Networks and Systems
paper · pdf · doi:10.48550/arxiv.2406.12717
openalex publication_date 2024/06/18 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
An st-shortest path, or st-path for short, in a graph G is a shortest (induced) path from s to t in G. Two st-paths are said to be adjacent if they differ on exactly one vertex. A reconfiguration sequence between two st-paths P and Q is a sequence of adjacent st-paths starting from P and ending at Q. Deciding whether there exists a reconfiguration sequence between two given st-paths is known to be PSPACE-complete, even on restricted classes of graphs such as graphs of bounded bandwidth (hence pathwidth). On the positive side, and rather surprisingly, the problem is polynomial-time solvable on planar graphs. In this paper, we study the parameterized complexity of the Shortest Path Reconfiguration (SPR) problem. We show that SPR is W[1]-hard parameterized by k + ℓ, even when restricted to graphs of bounded (constant) degeneracy; here k denotes the number of edges on an st-path, and ℓ denotes the length of a reconfiguration sequence from P to Q. We complement our hardness result by establishing the fixed-parameter tractability of SPR parameterized by ℓ and restricted to nowhere-dense classes of graphs. Additionally, we establish fixed-parameter tractability of SPR when parameterized by the treedepth, by the cluster-deletion number, or by the modular-width of the input graph.