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 -