Parameterized Shortest Path Reconfiguration
<|reference_start|>Parameterized Shortest Path Reconfiguration: 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 + \ell, even when restricted to graphs of bounded (constant) degeneracy; here k denotes the number of edges on an st-path, and \ell 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 \ell 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.<|reference_end|>
@article{bousquet2024parameterized,
    title={Parameterized Shortest Path Reconfiguration},
    author={Nicolas Bousquet and Kshitij Gajjar and Abhiruk Lahiri and Amer E.
  Mouawad},
    journal={arXiv preprint arXiv:2406.12717},
    year={2024},
    archivePrefix={arXiv},
    eprint={2406.12717},
    primaryClass={cs.CC cs.DS math.CO}
}