26 września 2025 10:15
[Seminarium ZOK] Daniel Dadush: "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^{\omega + o(1)}-time strongly polynomial time algorithm for computing a maximum bipartite b-matching where \omega is the matrix multiplication constant. Additionally, they imply an m^{1 + o(1)} W-time algorithm for solving the problem on graphs of treewidth 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, Kyng, Liu, Peng, Gutenberg, Sachdeva (FOCS 2022) and Brand, Chen, Kyng, Liu, Peng, Gutenberg, Sachdeva, Sidford (FOCS 2023), and by developing new incremental transitive cover data structures for special cases.
Joint work with Jim Orlin, Aaron Sidford, and Laszlo Vegh