Abstract: The Shortest Path Reconfiguration problem has as input a graph G (with unit edge lengths) with vertices s and t, and two shortest st-paths P and Q. The question is whether there exists a sequence of shortest st-paths that starts with P and ends with Q, such that subsequent paths differ in only one vertex. This is called a rerouting sequence. This problem is shown to be PSPACE-complete. For claw-free graphs and chordal graphs, it is shown that the problem can be solved in polynomial time, and that shortest rerouting sequences have linear length. For these classes, it is also shown that deciding whether a rerouting sequence exists between all pairs of shortest st-paths can be done in polynomial time. Finally, a polynomial time algorithm for counting the number of isolated paths is given.
Recommendations
Cites work
- Complexity of independent set reconfigurability problems
- Connectedness of the graph of vertex-colourings
- Finding paths between 3-colorings
- Finding paths between graph colourings: PSPACE-completeness and superpolynomial distances
- Graph theory
- Mixing 3-colourings in bipartite graphs
- Motion planning with pulley, rope, and baskets
- On the Complexity of Reconfiguration Problems
- On the complexity of reconfiguration problems
- PSPACE-completeness of sliding-block puzzles and other problems through the nondeterministic constraint logic model of computation
- Reconfiguration of List Edge-Colorings in a Graph
- Relationships between nondeterministic and deterministic tape complexities
- Rerouting shortest paths in planar graphs
- Shortest Paths between Shortest Paths and Independent Sets
- Shortest paths between shortest paths
- The Connectivity of Boolean Satisfiability: Computational and Structural Dichotomies
- The structure of claw-free graphs
Cited in
(36)- Independent set reconfiguration in cographs and their generalizations
- Using contracted solution graphs for solving reconfiguration problems
- Reconfiguration of Minimum Steiner Trees via Vertex Exchanges
- Rerouting shortest paths in planar graphs
- On reconfigurability of target sets
- Algorithms – ESA 2004
- Congestion-free rerouting of flows on DAGs
- The shortest path reconfiguration problem based on relaxation of reconfiguration rules
- On the complexity of distance-\(d\) independent set reconfiguration
- Reconfiguration on nowhere dense graph classes
- On the complexity of an optimal routing tree problem
- A reconfigurations analogue of Brooks' theorem and its consequences
- Reconfiguration of vertex-disjoint shortest paths on graphs
- Link reversal routing with binary link labels: work complexity
- Reconfiguration in bounded bandwidth and tree-depth
- The complexity of rerouting shortest paths
- Shortest paths between shortest paths
- Reconfiguration of regular induced subgraphs
- Shifting paths to avoidable ones
- Reconfiguration graphs of shortest paths
- Reconfiguring shortest paths in graphs
- Direct routing: Algorithms and complexity
- On the complexity of the shortest-path broadcast problem
- Reconfiguration of vertex-disjoint shortest paths on graphs
- On reconfiguration graphs: an abstraction
- Classification of reconfiguration graphs of shortest path graphs with no induced 4-cycles
- The complexity of routing with few collisions
- The complexity of routing with collision avoidance
- Linear-time algorithm for sliding tokens on trees
- Reconfiguration of colorable sets in classes of perfect graphs
- Reconfiguring (non-spanning) arborescences
- Rerouting shortest paths in planar graphs
- The complexity of the characterization of networks supporting shortest-path interval routing.
- On the computational complexity of continuous routing
- Shortest path reoptimization vs resolution from scratch: a computational comparison
- Degree-constrained subgraph reconfiguration is in P
This page was built for publication: The complexity of rerouting shortest paths
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q392173)
