License: Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ICALP.2021.64
URN: urn:nbn:de:0030-drops-141337
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2021/14133/
Go to the corresponding LIPIcs Volume Portal

Evald, Jacob ; Fredslund-Hansen, Viktor ; Gutenberg, Maximilian Probst ; Wulff-Nilsen, Christian

Decremental APSP in Unweighted Digraphs Versus an Adaptive Adversary

pdf-format:
LIPIcs-ICALP-2021-64.pdf (1.0 MB)

Abstract

Given an unweighted digraph G = (V,E), undergoing a sequence of edge deletions, with m = |E|, n = |V|, we consider the problem of maintaining all-pairs shortest paths (APSP).
Whilst this problem has been studied in a long line of research [ACM'81, FOCS'99, FOCS'01, STOC'02, STOC'03, SWAT'04, STOC'13] and the problem of (1+ε)-approximate, weighted APSP was solved to near-optimal update time Õ(mn) by Bernstein [STOC'13], the problem has mainly been studied in the context of an oblivious adversary which fixes the update sequence before the algorithm is started. In this paper, we make significant progress on the problem for an adaptive adversary which can perform updates based on answers to previous queries:
- We first present a deterministic data structure that maintains the exact distances with total update time Õ(n³).
- We also present a deterministic data structure that maintains (1+ε)-approximate distance estimates with total update time Õ(√m n²/ε) which for sparse graphs is Õ(n^{2+1/2}/ε).
- Finally, we present a randomized (1+ε)-approximate data structure which works against an adaptive adversary; its total update time is Õ(m^{2/3}n^{5/3} + n^{8/3}/(m^{1/3}ε²)) which for sparse graphs is Õ(n^{2+1/3}/ε²). Our exact data structure matches the total update time of the best randomized data structure by Baswana et al. [STOC'02] and maintains the distance matrix in near-optimal time. Our approximate data structures improve upon the best data structures against an adaptive adversary which have Õ(mn²) total update time [JACM'81, STOC'03].

BibTeX - Entry

@InProceedings{evald_et_al:LIPIcs.ICALP.2021.64,
  author =	{Evald, Jacob and Fredslund-Hansen, Viktor and Gutenberg, Maximilian Probst and Wulff-Nilsen, Christian},
  title =	{{Decremental APSP in Unweighted Digraphs Versus an Adaptive Adversary}},
  booktitle =	{48th International Colloquium on Automata, Languages, and Programming (ICALP 2021)},
  pages =	{64:1--64:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-195-5},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{198},
  editor =	{Bansal, Nikhil and Merelli, Emanuela and Worrell, James},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2021/14133},
  URN =		{urn:nbn:de:0030-drops-141337},
  doi =		{10.4230/LIPIcs.ICALP.2021.64},
  annote =	{Keywords: Dynamic Graph Algorithm, Data Structure, Shortest Paths}
}

Keywords: Dynamic Graph Algorithm, Data Structure, Shortest Paths
Collection: 48th International Colloquium on Automata, Languages, and Programming (ICALP 2021)
Issue Date: 2021
Date of publication: 02.07.2021

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI