Incremental Approximate Maximum Flow in m^1/2+o(1) update time

2022/11/17 by Goranci, Gramoz, Henzinger, Monika
#Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences

paper · doi:10.48550/arxiv.2211.09606

Abstract

We show an (1+ε)-approximation algorithm for maintaining maximum s-t flow under m edge insertions in m^1/2+o(1) ε^-1/2 amortized update time for directed, unweighted graphs. This constitutes the first sublinear dynamic maximum flow algorithm in general sparse graphs with arbitrarily good approximation guarantee.

Related

• Incremental Approximate Maximum Flow on Undirected Graphs in Subpolynomial Update Time
• Incremental Approximate Maximum Flow via Residual Graph Sparsification
• A Deterministic Almost-Linear Time Algorithm for Minimum-Cost Flow
• Dynamic Maxflow via Dynamic Interior Point Methods
• Maximum Flow and Minimum-Cost Flow in Almost-Linear Time