# Parameterized Shortest Path Reconfiguration

Preprint · Nicolas Bousquet, Kshitij Gajjar, Abhiruk Lahiri, Amer E. Mouawad

- Archive id: arxiv:2406.12717
- Published: 2024-06-18
- arXiv: https://arxiv.org/abs/2406.12717
- Source URL: https://arxiv.org/abs/2406.12717
- PDF: https://arxiv.org/pdf/2406.12717
- Provenance: arxiv

## Abstract

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.

_Abstract reproduced under CC0-1.0 (arXiv descriptive metadata)._

---
Space Kitty Archive · https://space-kitty.com · API: https://space-kitty.com/api/v1 · MCP: https://space-kitty.com/mcp · Premium: $0.20/request via x402 (Base Sepolia (testnet)). Metadata: arXiv (CC0), OpenAlex (CC0), Europe PMC (CC BY/CC0 works), ClinicalTrials.gov.