The Shortest Path Reconfiguration Problem Based on Relaxation of Reconfiguration Rules

The shortest path problem is the most classical and fundamental problem in the field of graph algorithm. Recently, its reconfiguration variant, namely the Shortest Path Reconfiguration problem, has received a lot of attention. In this paper, we study the complexity of k-SPR, which generalizes the Shortest Path Reconfiguration problem, with respect to k. In k-SPR, we are allowed to replace at most k consecutive vertices of the current shortest path at a time. We first show that, for any fixed rational numbers c and \(\varepsilon \) such that \(c > 0\) and \(0 < \varepsilon \le 1\) , k-SPR with \(k = cn^{1-\varepsilon }\) is polynomially solvable if \(\varepsilon = 1\) and \(c < 1\) ; otherwise, PSPACE-complete. This intractability holds even when given graphs are restricted to bipartite graphs and r-th power graphs, where r is any positive integer. Furthermore, when we restrict \(0 < \varepsilon < 1\) , the PSPACE-completeness holds for graphs with maximum degree 3. Then, we design an FPT algorithm parameterized by \(\mu = n/2 - k \ge 0\) that runs in \(O(m + 6.730^{\mu } \mu ^4 n)\) time. Finally, we show that, for any k, k-SPR can be solved in linear time for \(K_{2,3}\) -minor-free graphs.