Deterministic Decremental SSSP and Approximate Min-Cost Flow in Almost-Linear Time

Understand

In the decremental single-source shortest paths problem, the goal is to maintain distances from a fixed source $s$ to every vertex $v$ in an $m$-edge graph undergoing edge deletions.

• In this paper, we conclude a long line of research on this problem by showing a near-optimal deterministic data structure that maintains $(1+\epsilon)$-approximate distance estimates and runs in $m^{1+o(1)}$ total update time.
• Our result, in particular, removes the oblivious adversary assumption required by the previous breakthrough result by Henzinger et al.
• [FOCS'14], which leads to our second result: the first almost-linear time algorithm for $(1-\epsilon)$-approximate min-cost flow in undirected graphs where capacities and costs can be taken over edges and vertices.