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 \tilde  (n) in polylog(n) amortized update time. The second algorithm maintains an O(k)-approximate cut sparsifier of size \tilde  (n) in \tilde  (n^{1/k}) amortized update time, for any k\ge1, 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 ]
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 \tilde O (n) in polylog(n) amortized update time. The second algorithm maintains an O(k)-approximate cut sparsifier of size \tilde O (n) in \tilde O (n^{1/k}) amortized update time, for any k\ge1, which is polylog(n) time when k=\log(n). The third algorithm maintains a polylog(n)-approximate spectral sparsifier in polylog(n) amortized update time . 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. The first technique, is 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 technique we call proactive resampling. [ ... ]
A
O
A
O
A
O
A
third algorithm maintains a polylog(n)-approximate spectral sparsifier in polylog(n)
A
. The amortized update time
R
First of all, we show
The first technique, is
R
is a new technique called
technique we call
R
Abstract was shortened
...