Almost-Linear Time Algorithms for Decremental Graphs: Min-Cost Flow and More via Duality
Authors:
- 27 October 2024
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- p. 2010-2032
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 [ $\text{Goranci-Racke-}$ SaranurakTan, 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
Funding Information
- National Science Foundation (DMS-1926686)
This publication has 57 references indexed in Scilit:
- Bipartite Matching in Nearly-linear Time on Moderately Dense Graphs2020
- Near-Optimal Approximate Decremental All Pairs Shortest Paths2018
- Decremental Single-Source Reachability and Strongly Connected Components in Õ(m√n) Total Update Time2016
- Computing Maximum Flow with Augmenting Electrical Flows2016
- Improved Algorithms for Decremental Single-Source Reachability on Directed Graphs2015
- Path Finding Methods for Linear Programming: Solving Linear Programs in Õ(vrank) Iterations and Faster Algorithms for Maximum Flow2014
- Nearly Maximum Flows in Nearly Linear Time2013
- Navigating Central Path with Electrical Flows: From Flows to Matchings, and Back2013
- Fast Approximation Algorithms for Cut-Based Problems in Undirected Graphs2010
- A data structure for dynamic treesJournal of Computer and System Sciences, 1983