2026-07-21T23:57:34Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:22249 2024-12-05T15:32:41Z ddc:004 open_access

Parameterized Shortest Path Reconfiguration Bousquet, Nicolas Gajjar, Kshitij Lahiri, Abhiruk Mouawad, Amer E. combinatorial reconfiguration shortest path reconfiguration parameterized complexity structural parameters treedepth cluster deletion number modular width 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Nicolas Bousquet and Kshitij Gajjar and Abhiruk Lahiri and Amer E. Mouawad 2024 Is Part Of LIPIcs, Volume 321, 19th International Symposium on Parameterized and Exact Computation (IPEC 2024) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.IPEC.2024.23 urn:nbn:de:0030-drops-222491 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.IPEC.2024.23 eng https://creativecommons.org/licenses/by/4.0/legalcode