# Reconfiguring Shortest Paths in Graphs

arXiv: https://arxiv.org/abs/2112.07499 · HTML: https://mlsanity.com/paper/2112.07499/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 9 of its 72 references that are in the map.
- First posted on arXiv 14 Dec 2021.

## Builds on (most cited first, 9 of 9)

- [Solving the Rubik's Cube Optimally is NP-complete](https://mlsanity.com/paper/1706.06708/) (2017)
- [Coordinated Motion Planning: Reconfiguring a Swarm of Labeled Robots with Bounded Stretch](https://mlsanity.com/paper/1801.01689/) (2018)
- [Shortest reconfiguration paths in the solution space of Boolean formulas](https://mlsanity.com/paper/1404.3801/) (2014)
- [A Novel Dynamic Programming Approach to the Train Marshalling Problem](https://mlsanity.com/paper/1903.08364/) (2019)
- [On the Parameterized Complexity of Reconfiguration Problems](https://mlsanity.com/paper/1308.2409/) (2013)
- [Vertex Cover Reconfiguration and Beyond](https://mlsanity.com/paper/1402.4926/) (2014)
- [Reconfiguration on sparse graphs](https://mlsanity.com/paper/1502.04803/) (2015)
- [Characterizing minimum-length coordinated motions for two discs](https://mlsanity.com/paper/1607.04005/) (2016)
- [Distance-preserving Subgraphs of Interval Graphs](https://mlsanity.com/paper/1708.03081/) (2017)

## Abstract (arXiv)

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, (c) the shipping container stowage problem, and (d) the train marshalling problem. When modelled as graph problems, (a) is the most general case while (b), (c) and (d) are restrictions to different graph classes. We show that (a) is intractable, even for relaxed variants of the problem. For (b), (c) 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≥ 2) contiguous vertices on a shortest path can be changed at a time.