Shortest Paths between Shortest Paths and Independent Sets

DOI10.1007/978-3-642-19222-7_7zbMATH Open1326.05071arXiv1008.4563OpenAlexW3125407811MaRDI QIDQ3000494FDOQ3000494

Authors: Marcin Kamiński, Paul Medvedev, Martin Milanič 

Publication date: 19 May 2011

Published in: Lecture Notes in Computer Science (Search for Journal in Brave)

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_4$-free graphs).

Full work available at URL: https://arxiv.org/abs/1008.4563

Recommendations

• scientific article; zbMATH DE number 3105908
• Shortest paths between shortest paths
• Disjoint shortest paths in graphs
• Shortest edge-disjoint paths in graphs
• Independent sets which meet all longest paths
• Smallest sets of longest paths with empty intersection
• Shortest paths in reachability graphs
• scientific article; zbMATH DE number 617118
• Shortest paths in Sierpiński graphs
• The disjoint shortest paths problem

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Paths and cycles (05C38)

Cites Work

• Complement reducible graphs
• PSPACE-completeness of sliding-block puzzles and other problems through the nondeterministic constraint logic model of computation
• The strong perfect graph theorem
• Mixing 3-colourings in bipartite graphs
• Connectedness of the graph of vertex-colourings
• A Linear Recognition Algorithm for Cographs
• Finding paths between graph colourings: PSPACE-completeness and superpolynomial distances
• Reconfiguration of List Edge-Colorings in a Graph
• The Connectivity of Boolean Satisfiability: Computational and Structural Dichotomies
• On the Complexity of Reconfiguration Problems
• Even-hole-free graphs part II: Recognition algorithm
• Finding Paths between Graph Colourings: Computational Complexity and Possible Distances

Cited In (12)

• The complexity of rerouting shortest paths
• Title not available (Why is that?)
• Independent sets which meet all longest paths
• Complexity of independent set reconfigurability problems
• Shortest paths between shortest paths
• Shifting paths to avoidable ones
• Reconfiguring shortest paths in graphs
• Smallest sets of longest paths with empty intersection
• Reconfiguration of list edge-colorings in a graph
• The connectivity of Boolean satisfiability: dichotomies for formulas and circuits
• Reconfiguration graphs for vertex colourings of chordal and chordal bipartite graphs
• Reconfiguration of cliques in a graph

This page was built for publication: Shortest Paths between Shortest Paths and Independent Sets

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3000494)