Dynamic graph algorithms against an adaptive adversary via Congestion Balancing
Host
Quanquan Liu
MIT
I will talk about a new technique called congestion balancing which allows us to obtain several strong dynamic graph algorithms against an adaptive adversary including:
1. A near-optimal decremental single-source shortest path algorithm. This essential closes a long line of work on this problem. Moreover, it implies the first almost-linear time algorithms for computing (1+eps)-approximate min-cost flow on undirected vertex-capacitated graphs, which in turn implies many other applications.
2. A decremental single-source reachability algorithm O(mn^{2/3})-total-update time, breaking the O(mn) bound barrier since 1981 by [Even-Shiloach]
3. A near-optimal decremental bipartite matching.
I will explain the technique in a tutorial style (it should be easy-going) and explain on a high level why it is applicable for other problems.
Based on two papers with Aaron Bernstein and Maximilian Probst Gutenberg
https://arxiv.org/abs/2101.07149 https://arxiv.org/abs/2009.02584
1. A near-optimal decremental single-source shortest path algorithm. This essential closes a long line of work on this problem. Moreover, it implies the first almost-linear time algorithms for computing (1+eps)-approximate min-cost flow on undirected vertex-capacitated graphs, which in turn implies many other applications.
2. A decremental single-source reachability algorithm O(mn^{2/3})-total-update time, breaking the O(mn) bound barrier since 1981 by [Even-Shiloach]
3. A near-optimal decremental bipartite matching.
I will explain the technique in a tutorial style (it should be easy-going) and explain on a high level why it is applicable for other problems.
Based on two papers with Aaron Bernstein and Maximilian Probst Gutenberg
https://arxiv.org/abs/2101.07149 https://arxiv.org/abs/2009.02584