Shortest paths between shortest paths and independent sets

Marcin Kaminski, Paul Medvedev, Martin Milanic

We study problems of reconfiguration of shortest paths in graphs. We prove that the shortest reconfiguration sequence can be exponential in the size of the graph and that it is NP-…