From Incremental Transitive Cover to Strongly Polynomial Maximum Flow

We provide faster strongly polynomial time algorithms solving maximum flow in structured n-node m-arc networks. Our results imply an n ω+o(1) -time strongly polynomial time algorithms for computing a maximum bipartite b-matching where ω is the matrix multiplication constant. Additionally, they imply an m 1+o(1) W -time algorithm for solving the problem on graphs with a given tree decomposition of width W .

We obtain these results by strengthening and efficiently implementing an approach in Orlin's (STOC 2013) state-of-the-art O(mn) time maximum flow algorithm. We develop a general framework that reduces solving maximum flow with arbitrary capacities to (1) solving a sequence of maximum flow problems with polynomial bounded capacities and (2) dynamically maintaining a size-bounded supersets of the transitive closure under arc additions; we call this problem incremental transitive cover. Our applications follow by leveraging recent weakly polynomial, almost linear time algorithms for maximum flow due to Chen,