Dynamic Maxflow via Dynamic Interior Point Methods
Preprint
Abstract
In this paper we provide an algorithm for maintaining a $(1-\epsilon)$-approximate maximum flow in a dynamic, capacitated graph undergoing edge additions. Over a sequence of $m$-additions to an $n$-node graph where every edge has capacity $O(\mathrm{poly}(m))$ our algorithm runs in time $\widehat{O}(m \sqrt{n} \cdot \epsilon^{-1})$. To obtain this result we design dynamic data structures for the more general problem of detecting when the value of the minimum cost circulation in a dynamic graph undergoing edge additions obtains value at most $F$ (exactly) for a given threshold $F$. Over a sequence $m$-additions to an $n$-node graph where every edge has capacity $O(\mathrm{poly}(m))$ and cost $O(\mathrm{poly}(m))$ we solve this thresholded minimum cost flow problem in $\widehat{O}(m \sqrt{n})$. Both of our algorithms succeed with high probability against an adaptive adversary. We obtain these results by dynamizing the recent interior point method used to obtain an almost linear time algorithm for minimum cost flow (Chen, Kyng, Liu, Peng, Probst Gutenberg, Sachdeva 2022), and introducing a new dynamic data structure for maintaining minimum ratio cycles in an undirected graph that succeeds with high probability against adaptive adversaries.
Keywords
All Related Versions
This publication has 43 references indexed in Scilit:
- Faster Sparse Minimum Cost Flow by Electrical Flow Localization2022
- Fully Dynamic Electrical Flows: Sparse Maxflow Faster Than Goldberg-Rao2022
- Dynamic Matrix Inverse: Improved Algorithms and Matching Conditional Lower Bounds2019
- Fully Dynamic Maximal Independent Set in Expected Poly-Log Update Time2019
- Popular Conjectures as a Barrier for Dynamic Planar Graph Algorithms2016
- Fully Dynamic Maximal Matching in Constant Update Time2016
- Online Bipartite Matching in Offline Time2014
- Fully Dynamic (1+ e)-Approximate Matchings2013
- An Incremental Algorithm for the Maximum Flow ProblemJournal of Mathematical Modelling and Algorithms, 2003
- Amortized efficiency of a path retrieval data structureTheoretical Computer Science, 1986