Almost-Linear Time Algorithms for Decremental Graphs: Min-Cost Flow and More via Duality
<|reference_start|>Almost-Linear Time Algorithms for Decremental Graphs: Min-Cost Flow and More via Duality: 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\"{a}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.<|reference_end|>
@article{brand2024almost-linear,
    title={Almost-Linear Time Algorithms for Decremental Graphs: Min-Cost Flow and
  More via Duality},
    author={Jan van den Brand and Li Chen and Rasmus Kyng and Yang P. Liu and
  Simon Meierhans and Maximilian Probst Gutenberg and Sushant Sachdeva},
    journal={arXiv preprint arXiv:2407.10830},
    year={2024},
    archivePrefix={arXiv},
    eprint={2407.10830},
    primaryClass={cs.DS}
}