DROPS

Document

Track A: Algorithms, Complexity and Games

DOI: 10.4230/LIPIcs.ICALP.2020.81

Near Optimal Algorithm for the Directed Single Source Replacement Paths Problem

Authors: Shiri Chechik and Ofer Magen

Published in: LIPIcs, Volume 168, 47th International Colloquium on Automata, Languages, and Programming (ICALP 2020)

Abstract

In the Single Source Replacement Paths (SSRP) problem we are given a graph G = (V, E), and a shortest paths tree K̂ rooted at a node s, and the goal is to output for every node t ∈ V and for every edge e in K̂ the length of the shortest path from s to t avoiding e. We present an Õ(m√n + n²) time randomized combinatorial algorithm for unweighted directed graphs. Previously such a bound was known in the directed case only for the seemingly easier problem of replacement path where both the source and the target nodes are fixed. Our new upper bound for this problem matches the existing conditional combinatorial lower bounds. Hence, (assuming these conditional lower bounds) our result is essentially optimal and completes the picture of the SSRP problem in the combinatorial setting. Our algorithm naturally extends to the case of small, rational edge weights. In the full version of the paper, we strengthen the existing conditional lower bounds in this case by showing that any O(mn^(1/2-ε)) time (combinatorial or algebraic) algorithm for some fixed ε > 0 yields a truly sub-cubic algorithm for the weighted All Pairs Shortest Paths problem (previously such a bound was known only for the combinatorial setting).

Cite as

Shiri Chechik and Ofer Magen. Near Optimal Algorithm for the Directed Single Source Replacement Paths Problem. In 47th International Colloquium on Automata, Languages, and Programming (ICALP 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 168, pp. 81:1-81:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{chechik_et_al:LIPIcs.ICALP.2020.81,
  author =	{Chechik, Shiri and Magen, Ofer},
  title =	{{Near Optimal Algorithm for the Directed Single Source Replacement Paths Problem}},
  booktitle =	{47th International Colloquium on Automata, Languages, and Programming (ICALP 2020)},
  pages =	{81:1--81:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-138-2},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{168},
  editor =	{Czumaj, Artur and Dawar, Anuj and Merelli, Emanuela},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2020.81},
  URN =		{urn:nbn:de:0030-drops-124886},
  doi =		{10.4230/LIPIcs.ICALP.2020.81},
  annote =	{Keywords: Fault tolerance, Replacement Paths, Combinatorial algorithms, Conditional lower bounds}
}

Search Results

Documents authored by Magen, Ofer

Near Optimal Algorithm for the Directed Single Source Replacement Paths Problem

Abstract

Cite as

Thanks for your feedback!

Could not send message