Fully-Dynamic Graph Sparsifiers Against an Adaptive Adversary

Understand

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.