Almost-Linear Time Algorithms for Decremental Graphs: Min-Cost Flow and More via Duality
Preprint
Abstract
We give the first almost-linear total time algorithm for deciding if a flow of cost at most $F$ still exists in a directed graph, with edge costs and capacities, undergoing decremental updates, i.e., edge deletions, capacity decreases, and cost increases. This implies almost-linear time algorithms for approximating the minimum-cost flow value and $s$-$t$ distance on such decremental graphs. Our framework additionally allows us to maintain decremental strongly connected components in almost-linear time deterministically. These algorithms also improve over the current best known runtimes for statically computing minimum-cost flow, in both the randomized and deterministic settings. We obtain our algorithms by taking the dual perspective, which yields cut-based algorithms. More precisely, our algorithm computes the flow via a sequence of $m^{1+o(1)}$ dynamic min-ratio cut problems, the dual analog of the dynamic min-ratio cycle problem that underlies recent fast algorithms for minimum-cost flow. Our main technical contribution is a new data structure that returns an approximately optimal min-ratio cut in amortized $m^{o(1)}$ time by maintaining a tree-cut sparsifier. This is achieved by devising a new algorithm to maintain the dynamic expander hierarchy of [Goranci-Räcke-Saranurak-Tan, SODA 2021] that also works in capacitated graphs. All our algorithms are deterministc, though they can be sped up further using randomized techniques while still working against an adaptive adversary.
Keywords
All Related Versions
This publication has 13 references indexed in Scilit:
- Entropy Regularization and Faster Decremental Matching in General Graphs2025
- Dynamic (1+ϵ)-Approximate Matching Size in Truly Sublinear Update Time2023
- A Deterministic Algorithm for Balanced Cut with Applications to Dynamic Connectivity, Flows, and Beyond2020
- Decremental Single-Source Shortest Paths on Undirected Graphs in Near-Linear Total Update TimeJournal of the ACM, 2018
- Approximate Undirected Maximum Flows in O(mpolylog(n)) Time2015
- Unifying and Strengthening Hardness for Dynamic Problems via the Online Matrix-Vector Multiplication Conjecture2015
- Navigating Central Path with Electrical Flows: From Flows to Matchings, and Back2013
- Graph partitioning using single commodity flowsJournal of the ACM, 2009
- Faster and Simpler Algorithms for Multicommodity Flow and Other Fractional Packing ProblemsSIAM Journal on Computing, 2007
- Maintaining information in fully dynamic trees with top treesACM Transactions on Algorithms, 2005