From Incremental Transitive Cover to Strongly Polynomial Maximum Flow

Daniel Dadush; James B. Orlin; Aaron Sidford; László A. Végh

doi:10.1137/1.9781611978971.7

From Incremental Transitive Cover to Strongly Polynomial Maximum Flow

Daniel Dadush
, James B. Orlin
, Aaron Sidford
, László A. Végh

Sub Mathematical Modeling

Massachusetts Institute of Technology
Stanford University
University of Bonn

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-review

Abstract

We provide faster strongly polynomial time algorithms solving maximum flow in structured nnode m-arc networks. Our results imply an n^ω⁺^o⁽¹⁾-time strongly polynomial time algorithms for computing a maximum bipartite b-matching where ω is the matrix multiplication constant. Additionally, they imply an m¹⁺^o⁽¹⁾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, Kyng, Liu, Peng, Gutenberg, Sachdeva (FOCS 2022) and Brand, Chen, Kyng, Liu, Peng, Gutenberg, Sachdeva, Sidford (FOCS 2023), and by developing incremental transitive cover data structures.

Original language	English
Title of host publication	Proceedings of the 2026 Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2026
Editors	Kasper Green Larsen, Barna Saha
Publisher	Association for Computing Machinery
Pages	150-163
Number of pages	14
ISBN (Electronic)	9781611978971
DOIs	https://doi.org/10.1137/1.9781611978971.7
Publication status	Published - 7 Jan 2026
Event	37th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2026 - Vancouver, Canada Duration: 11 Jan 2026 → 14 Jan 2026

Publication series

Name	Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms
Volume	2026-January
ISSN (Print)	1071-9040
ISSN (Electronic)	1557-9468

Conference

Conference	37th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2026
Country/Territory	Canada
City	Vancouver
Period	11/01/26 → 14/01/26

Bibliographical note

Publisher Copyright:
© 2026 Association for Computing Machinery. All rights reserved.

Access to Document

10.1137/1.9781611978971.7

Cite this

Dadush, D., Orlin, J. B., Sidford, A., & Végh, L. A. (2026). From Incremental Transitive Cover to Strongly Polynomial Maximum Flow. In K. G. Larsen, & B. Saha (Eds.), Proceedings of the 2026 Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2026 (pp. 150-163). (Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms; Vol. 2026-January). Association for Computing Machinery. https://doi.org/10.1137/1.9781611978971.7

Dadush, Daniel ; Orlin, James B. ; Sidford, Aaron et al. / From Incremental Transitive Cover to Strongly Polynomial Maximum Flow. Proceedings of the 2026 Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2026. editor / Kasper Green Larsen ; Barna Saha. Association for Computing Machinery, 2026. pp. 150-163 (Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms).

@inproceedings{a013380762354aebb7a2e0b2ee07ae9b,

title = "From Incremental Transitive Cover to Strongly Polynomial Maximum Flow",

abstract = "We provide faster strongly polynomial time algorithms solving maximum flow in structured nnode 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 m1+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{\textquoteright}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 incremental transitive cover data structures.",

author = "Daniel Dadush and Orlin, \{James B.\} and Aaron Sidford and V{\'e}gh, \{L{\'a}szl{\'o} A.\}",

note = "Publisher Copyright: {\textcopyright} 2026 Association for Computing Machinery. All rights reserved.; 37th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2026 ; Conference date: 11-01-2026 Through 14-01-2026",

year = "2026",

month = jan,

day = "7",

doi = "10.1137/1.9781611978971.7",

language = "English",

series = "Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms",

publisher = "Association for Computing Machinery",

pages = "150--163",

editor = "Larsen, \{Kasper Green\} and Barna Saha",

booktitle = "Proceedings of the 2026 Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2026",

}

Dadush, D, Orlin, JB, Sidford, A & Végh, LA 2026, From Incremental Transitive Cover to Strongly Polynomial Maximum Flow. in KG Larsen & B Saha (eds), Proceedings of the 2026 Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2026. Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms, vol. 2026-January, Association for Computing Machinery, pp. 150-163, 37th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2026, Vancouver, Canada, 11/01/26. https://doi.org/10.1137/1.9781611978971.7

From Incremental Transitive Cover to Strongly Polynomial Maximum Flow. / Dadush, Daniel; Orlin, James B.; Sidford, Aaron et al.
Proceedings of the 2026 Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2026. ed. / Kasper Green Larsen; Barna Saha. Association for Computing Machinery, 2026. p. 150-163 (Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms; Vol. 2026-January).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-review

TY - GEN

T1 - From Incremental Transitive Cover to Strongly Polynomial Maximum Flow

AU - Dadush, Daniel

AU - Orlin, James B.

AU - Sidford, Aaron

AU - Végh, László A.

PY - 2026/1/7

Y1 - 2026/1/7

N2 - We provide faster strongly polynomial time algorithms solving maximum flow in structured nnode 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 m1+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, Kyng, Liu, Peng, Gutenberg, Sachdeva (FOCS 2022) and Brand, Chen, Kyng, Liu, Peng, Gutenberg, Sachdeva, Sidford (FOCS 2023), and by developing incremental transitive cover data structures.

AB - We provide faster strongly polynomial time algorithms solving maximum flow in structured nnode 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 m1+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, Kyng, Liu, Peng, Gutenberg, Sachdeva (FOCS 2022) and Brand, Chen, Kyng, Liu, Peng, Gutenberg, Sachdeva, Sidford (FOCS 2023), and by developing incremental transitive cover data structures.

UR - https://www.scopus.com/pages/publications/105033695190

U2 - 10.1137/1.9781611978971.7

DO - 10.1137/1.9781611978971.7

M3 - Conference contribution

AN - SCOPUS:105033695190

T3 - Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms

SP - 150

EP - 163

BT - Proceedings of the 2026 Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2026

A2 - Larsen, Kasper Green

A2 - Saha, Barna

PB - Association for Computing Machinery

T2 - 37th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2026

Y2 - 11 January 2026 through 14 January 2026

ER -

Dadush D, Orlin JB, Sidford A, Végh LA. From Incremental Transitive Cover to Strongly Polynomial Maximum Flow. In Larsen KG, Saha B, editors, Proceedings of the 2026 Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2026. Association for Computing Machinery. 2026. p. 150-163. (Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms). doi: 10.1137/1.9781611978971.7

From Incremental Transitive Cover to Strongly Polynomial Maximum Flow

Abstract

Publication series

Conference

Bibliographical note

Access to Document

Other files and links

Fingerprint

Cite this