Deterministic combinatorial replacement paths and distance sensitivity oracles

Noga Alon, Shiri Chechik, Sarel Cohen

Research output: Chapter in Book/Report/Conference proceedingConference contribution

2 Scopus citations

Abstract

In this work we derandomize two central results in graph algorithms, replacement paths and distance sensitivity oracles (DSOs) matching in both cases the running time of the randomized algorithms. For the replacement paths problem, let G = (V, E) be a directed unweighted graph with n vertices and m edges and let P be a shortest path from s to t in G. The replacement paths problem is to find for every edge e ∈ P the shortest path from s to t avoiding e. Roditty and Zwick [ICALP 2005] obtained a randomized algorithm with running time of Oe(m√n). Here we provide the first deterministic algorithm for this problem, with the same Oe(m√n) time. Due to matching conditional lower bounds of Williams et al. [FOCS 2010], our deterministic combinatorial algorithm for the replacement paths problem is optimal up to polylogarithmic factors (unless the long standing bound of Oe(mn) for the combinatorial boolean matrix multiplication can be improved). This also implies a deterministic algorithm for the second simple shortest path problem in Oe(m√n) time, and a deterministic algorithm for the k-simple shortest paths problem in Oe(km√n) time (for any integer constant k > 0). For the problem of distance sensitivity oracles, let G = (V, E) be a directed graph with real-edge weights. An f-Sensitivity Distance Oracle (f-DSO) gets as input the graph G = (V, E) and a parameter f, preprocesses it into a data-structure, such that given a query (s, t, F) with s, t ∈ V and F ⊆ E ∪ V, |F| ≤ f being a set of at most f edges or vertices (failures), the query algorithm efficiently computes the distance from s to t in the graph G \ F (i.e., the distance from s to t in the graph G after removing from it the failing edges and vertices F). For weighted graphs with real edge weights, Weimann and Yuster [FOCS 2010] presented several randomized f-DSOs. In particular, they presented a combinatorial f-DSO with Oe(mn4α) preprocessing time and subquadratic Oe(n2−2(1−α)/f) query time, giving a tradeoff between preprocessing and query time for every value of 0 < α < 1. We derandomize this result and present a combinatorial deterministic f-DSO with the same asymptotic preprocessing and query time.

Original languageEnglish (US)
Title of host publication46th International Colloquium on Automata, Languages, and Programming, ICALP 2019
EditorsChristel Baier, Ioannis Chatzigiannakis, Paola Flocchini, Stefano Leonardi
PublisherSchloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
ISBN (Electronic)9783959771092
DOIs
StatePublished - Jul 1 2019
Event46th International Colloquium on Automata, Languages, and Programming, ICALP 2019 - Patras, Greece
Duration: Jul 9 2019Jul 12 2019

Publication series

NameLeibniz International Proceedings in Informatics, LIPIcs
Volume132
ISSN (Print)1868-8969

Conference

Conference46th International Colloquium on Automata, Languages, and Programming, ICALP 2019
CountryGreece
CityPatras
Period7/9/197/12/19

All Science Journal Classification (ASJC) codes

  • Software

Keywords

  • Derandomization
  • Distance sensitivity oracles
  • Replacement paths

Fingerprint Dive into the research topics of 'Deterministic combinatorial replacement paths and distance sensitivity oracles'. Together they form a unique fingerprint.

  • Cite this

    Alon, N., Chechik, S., & Cohen, S. (2019). Deterministic combinatorial replacement paths and distance sensitivity oracles. In C. Baier, I. Chatzigiannakis, P. Flocchini, & S. Leonardi (Eds.), 46th International Colloquium on Automata, Languages, and Programming, ICALP 2019 [12] (Leibniz International Proceedings in Informatics, LIPIcs; Vol. 132). Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing. https://doi.org/10.4230/LIPIcs.ICALP.2019.12