Dynamic Maxflow via Dynamic Interior Point Methods

In this paper we provide an algorithm for maintaining a (1−є)-approximate maximum flow in a dynamic, capacitated graph undergoing edge insertions. Over a sequence of m insertions to an n -node graph where every edge has capacity O ( poly ( m )) our algorithm runs in time O ( m √ n · є −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 insertions achieves value at most F (exactly) for a given threshold F . Over a sequence m insertions to an n -node graph where every edge has capacity O ( poly ( m )) and cost O ( poly ( m )) we solve this thresholded minimum cost flow problem in O ( m √ n ). Both of our algorithms succeed with high probability against an adaptive adversary. We obtain these results by dynamizing the recent interior point method by [Chen et al. ‍FOCS 2022] used to obtain an almost linear time algorithm for minimum cost flow, and introducing a new dynamic data structure for maintaining minimum ratio cycles in an undirected graph that succeeds with high probability against adaptive adversaries.

Authors

• Jan van den Brand
• Yang P. Liu
• Aaron Sidford

Keywords

• bipartite matching
• dynamic algorithm
• graph algorithm
• maximum flow
• minimum cost flow