Rerouting shortest paths in planar graphs
Paul Bonsma · Discrete Applied Mathematics · 2016
A rerouting sequence is a sequence of shortest st-paths such that consecutive paths differ in one vertex. We study the Shortest Path Rerouting Problem, which asks, given two shortest st-paths P and Q in a graph G, whether a rerouting sequence exists from P to Q. This problem is PSPACE-hard in general, but we show that it can be solved in polynomial time if G is planar. In addition, it can be solved in polynomial time when every vertex has at most two neighbors closer to s and at most two neighbors closer to t. To this end, we introduce a dynamic programming method for reconfiguration problems, based on using small encodings of reconfiguration graphs.