Fully-Dynamic Graph Sparsifiers Against an Adaptive Adversary
share
Designing dynamic graph algorithms against an adaptive adversary is a major goal in the field of dynamic graph algorithms. While a few such algorithms are known for spanning trees, matchings, and single-source shortest paths, very little was known for an important primitive like graph sparsifiers. The challenge is how to approximately preserve so much information about the graph (e.g., all-pairs distances and all cuts) without revealing the algorithms' underlying randomness to the adaptive adversary. In this paper we present the first non-trivial efficient adaptive algorithms for maintaining spanners and cut sparisifers. These algorithms in turn imply improvements over existing algorithms for other problems. Our first algorithm maintains a polylog(n)-spanner of size Õ(n) in polylog(n) amortized update time. The second algorithm maintains an O(k)-approximate cut sparsifier of size Õ(n) in Õ(n^1/k) amortized update time, for any k>1, which is polylog(n) time when k=log(n). The amortized update time of both algorithms can be made worst-case by paying some sub-polynomial factors. Prior to our result, there were near-optimal algorithms against oblivious adversaries (e.g. Baswana et al. [TALG'12] and Abraham et al. [FOCS'16]), but the only non-trivial adaptive dynamic algorithm requires O(n) amortized update time to maintain 3- and 5-spanner of size O(n^1+1/2) and O(n^1+1/3), respectively [Ausiello et al. ESA'05]. Our results are based on two novel techniques. First of all, we show a generic black-box reduction that allows us to assume that the graph undergoes only edge deletions and, more importantly, remains an expander with almost-uniform degree. The second is a new technique called proactive resampling. [Abstract was shortened]
READ FULL TEXT