Decremental APSP in unweighted digraphs versus an adaptive adversary
Research output: Chapter in Book/Report/Conference proceeding › Article in proceedings › Research › peer-review
Standard
Decremental APSP in unweighted digraphs versus an adaptive adversary. / Evald, Jacob; Fredslund-Hansen, Viktor; Gutenberg, Maximilian Probst; Wulff-Nilsen, Christian.
48th International Colloquium on Automata, Languages, and Programming, ICALP 2021. ed. / Nikhil Bansal; Emanuela Merelli; James Worrell. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2021. p. 1-20 64 (Leibniz International Proceedings in Informatics, LIPIcs, Vol. 198).Research output: Chapter in Book/Report/Conference proceeding › Article in proceedings › Research › peer-review
Harvard
APA
Vancouver
Author
Bibtex
}
RIS
TY - GEN
T1 - Decremental APSP in unweighted digraphs versus an adaptive adversary
AU - Evald, Jacob
AU - Fredslund-Hansen, Viktor
AU - Gutenberg, Maximilian Probst
AU - Wulff-Nilsen, Christian
N1 - Publisher Copyright: © 2021 Jacob Evald, Viktor Fredslund-Hansen, Maximilian Probst Gutenberg, and Christian Wulff-Nilsen.
PY - 2021
Y1 - 2021
N2 - 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 Õ(n3)1. ▪ We also present a deterministic data structure that maintains (1 + ∈)-approximate distance estimates with total update time Õ(√mn2/∈) which for sparse graphs is Õ(n2+1/2/∈). ▪ Finally, we present a randomized (1 + ∈)-approximate data structure which works against an adaptive adversary; its total update time is Õ(m2/3n5/3+n8/3/(m1/3∈2)) which for sparse graphs is Õ(n2+1/3/∈2). 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 Õ(mn2) total update time [JACM'81, STOC'03].
AB - 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 Õ(n3)1. ▪ We also present a deterministic data structure that maintains (1 + ∈)-approximate distance estimates with total update time Õ(√mn2/∈) which for sparse graphs is Õ(n2+1/2/∈). ▪ Finally, we present a randomized (1 + ∈)-approximate data structure which works against an adaptive adversary; its total update time is Õ(m2/3n5/3+n8/3/(m1/3∈2)) which for sparse graphs is Õ(n2+1/3/∈2). 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 Õ(mn2) total update time [JACM'81, STOC'03].
KW - Data structure
KW - Dynamic graph algorithm
KW - Shortest paths
UR - http://www.scopus.com/inward/record.url?scp=85115303883&partnerID=8YFLogxK
U2 - 10.4230/LIPIcs.ICALP.2021.64
DO - 10.4230/LIPIcs.ICALP.2021.64
M3 - Article in proceedings
AN - SCOPUS:85115303883
T3 - Leibniz International Proceedings in Informatics, LIPIcs
SP - 1
EP - 20
BT - 48th International Colloquium on Automata, Languages, and Programming, ICALP 2021
A2 - Bansal, Nikhil
A2 - Merelli, Emanuela
A2 - Worrell, James
PB - Schloss Dagstuhl - Leibniz-Zentrum für Informatik
T2 - 48th International Colloquium on Automata, Languages, and Programming, ICALP 2021
Y2 - 12 July 2021 through 16 July 2021
ER -
ID: 299757847