Reconfiguring Shortest Paths in Graphs

Reconfiguring two shortest paths in a graph means modifying one shortest path to the other by changing one vertex at a time so that all the intermediate paths are also shortest paths. This problem has several natural applications, namely: (a) revamping road networks, (b) rerouting data packets in synchronous multiprocessing setting, © the shipping container stowage problem, and (d) the train marshalling problem. When modelled as graph problems, (a) is the most general case while (b), © and (d) are restrictions to different graph classes. We show that (a) is intractable, even for relaxed variants of the problem. For (b), © and (d), we present efficient algorithms to solve the respective problems. We also generalize the problem to when at most $k$ (for a fixed integer $k\ge 2$) contiguous vertices on a shortest path can be changed at a time.