Shortest paths between shortest paths and independent sets

2010/08/31 by Marcin Kaminski, Paul Medvedev, Martin Milanic · 1 citation
Computer Science · #cs.CC #cs.DM

paper · pdf · doi:10.1007/978-3-642-19222-7_7

arxiv created 2011/02/07 · arxiv updated 2015/05/19

Abstract

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-hard to compute the shortest reconfiguration sequence even when we know that the sequence has polynomial length. Moreover, we also study reconfiguration of independent sets in three different models and analyze relationships between these models, observing that shortest path reconfiguration is a special case of independent set reconfiguration in perfect graphs, under any of the three models. Finally, we give polynomial results for restricted classes of graphs (even-hole-free and P₄-free graphs).

Cited by

• Separating Feasibility and Movement in Solution Discovery: The Case of Path Discovery

Related

• Reconfiguration of Cliques in a Graph
• Extremal Independent Set Reconfiguration
• Classification of Reconfiguration Graphs of Shortest Path Graphs With No Induced 4-cycles
• Reconfiguration graphs of shortest paths
• Reconfiguring Shortest Paths in Graphs