Reconfiguration of vertex-disjoint shortest paths on graphs

Abstract

We introduce and study reconfiguration problems for (internally) vertex-disjoint shortest paths:
Given two tuples of internally vertex-disjoint shortest paths for fixed terminal pairs in an unweighted graph, we are asked to determine whether one tuple can be transformed into the other by exchanging a single vertex of one shortest path in the tuple at a time, so that all intermediate results remain tuples of internally vertex-disjoint shortest paths.
We also study the shortest variant of the problem, that is, we wish to minimize the number of vertex-exchange steps required for such a transformation, if exists.
These problems generalize the well-studied Shortest Path Reconfiguration problem.
In this paper, we analyze the complexity of these problems from the viewpoint of graph classes, and give some interesting contrast.