{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,2]],"date-time":"2026-03-02T16:16:52Z","timestamp":1772468212941,"version":"3.50.1"},"reference-count":36,"publisher":"Association for Computing Machinery (ACM)","issue":"4","funder":[{"name":"NSF award","award":["CCF-1907820, CCF-1955703"],"award-info":[{"award-number":["CCF-1907820, CCF-1955703"]}]},{"name":"NSF CAREER award","award":["CCF-1750140"],"award-info":[{"award-number":["CCF-1750140"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["J. ACM"],"published-print":{"date-parts":[[2025,8,31]]},"abstract":"<jats:p>\n            We give a deterministic algorithm for finding the minimum (weight) cut of an undirected graph on\n            <jats:italic toggle=\"yes\">n<\/jats:italic>\n            vertices and\n            <jats:italic toggle=\"yes\">m<\/jats:italic>\n            edges using polylog (\n            <jats:italic toggle=\"yes\">n<\/jats:italic>\n            ) calls to a black box maximum flow subroutine. Using the current best deterministic maximum flow algorithms, this marks the first improvement for this problem since a running time bound of\n            <jats:inline-formula content-type=\"math\/tex\">\n              <jats:tex-math notation=\"LaTeX\" version=\"MathJax\">\\(\\tilde{O}(mn)\\)<\/jats:tex-math>\n            <\/jats:inline-formula>\n            was established by several papers in the early 1990s.\n          <\/jats:p>\n          <jats:p>Our global minimum cut algorithm is obtained as a corollary of a deterministic minimum Steiner cut algorithm, where a minimum Steiner cut is a minimum (weight) set of edges whose removal disconnects at least one pair of vertices among a designated set of terminal vertices. We also give a remarkably simple randomized minimum Steiner cut algorithm that still improves the best known randomized algorithm for the problem.<\/jats:p>\n          <jats:p>\n            Our main technical contribution is a new tool that we call\n            <jats:italic toggle=\"yes\">isolating cuts<\/jats:italic>\n            . Given a set of vertices\n            <jats:italic toggle=\"yes\">R<\/jats:italic>\n            , this entails finding cuts of minimum weight that separate (or isolate) each individual vertex\n            <jats:inline-formula content-type=\"math\/tex\">\n              <jats:tex-math notation=\"LaTeX\" version=\"MathJax\">\\(v\\in R\\)<\/jats:tex-math>\n            <\/jats:inline-formula>\n            from the rest of the vertices\n            <jats:inline-formula content-type=\"math\/tex\">\n              <jats:tex-math notation=\"LaTeX\" version=\"MathJax\">\\(R\\setminus \\lbrace v\\rbrace\\)<\/jats:tex-math>\n            <\/jats:inline-formula>\n            . Na\u00efvely, this can be done using\n            <jats:italic toggle=\"yes\">|R|<\/jats:italic>\n            maximum flow calls, but we show that just\n            <jats:italic toggle=\"yes\">O<\/jats:italic>\n            (log\n            <jats:italic toggle=\"yes\">|R|<\/jats:italic>\n            ) calls on graphs containing\n            <jats:italic toggle=\"yes\">O(n)<\/jats:italic>\n            vertices and\n            <jats:italic toggle=\"yes\">O(m)<\/jats:italic>\n            edges suffice. We call this the\n            <jats:italic toggle=\"yes\">isolating cut lemma<\/jats:italic>\n            .\n          <\/jats:p>","DOI":"10.1145\/3744737","type":"journal-article","created":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T21:18:38Z","timestamp":1750281518000},"page":"1-18","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":1,"title":["Deterministic Minimum Cut in Poly-logarithmic Maximum Flows"],"prefix":"10.1145","volume":"72","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-3644-0879","authenticated-orcid":false,"given":"Jason","family":"Li","sequence":"first","affiliation":[{"name":"Carnegie Mellon University","place":["Pittsburgh, United States"]}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-1799-6660","authenticated-orcid":false,"given":"Debmalya","family":"Panigrahi","sequence":"additional","affiliation":[{"name":"Department of Computer Science, Duke University","place":["Durham, United States"]}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2025,7,24]]},"reference":[{"key":"e_1_3_4_2_2","doi-asserted-by":"crossref","unstructured":"Amir Abboud Robert Krauthgamer Jason Li Debmalya Panigrahi Thatchaphol Saranurak and Ohad Trabelsi. 2022. Breaking the cubic barrier for all-pairs max-flow: Gomory-Hu tree in nearly quadratic time. In Proceedings of the IEEE 63rd Annual Symposium on Foundations of Computer Science (FOCS 2022). 884\u2013895.","DOI":"10.1109\/FOCS54457.2022.00088"},{"key":"e_1_3_4_3_2","volume-title":"Proceedings of the Foundations of Computer Science (FOCS), 2021 IEEE 62nd Annual Symposium on","author":"Abboud Amir","year":"2021","unstructured":"Amir Abboud, Robert Krauthgamer, and Ohad Trabelsi. 2021. APMF < APSP? Gomory-Hu tree for unweighted graphs in almost-quadratic time. In Proceedings of the Foundations of Computer Science (FOCS), 2021 IEEE 62nd Annual Symposium on."},{"key":"e_1_3_4_4_2","first-page":"1725","volume-title":"Proceedings of the STOC \u201921: 53rd Annual ACM SIGACT Symposium on Theory of Computing, Virtual Event, Italy, June 21\u201325, 2021","author":"Abboud Amir","year":"2021","unstructured":"Amir Abboud, Robert Krauthgamer, and Ohad Trabelsi. 2021. Subcubic algorithms for Gomory-Hu tree in unweighted graphs. In Proceedings of the STOC \u201921: 53rd Annual ACM SIGACT Symposium on Theory of Computing, Virtual Event, Italy, June 21\u201325, 2021, Samir Khuller and Virginia Vassilevska Williams (Eds.). ACM, 1725\u20131737. DOI:10.1145\/3406325.3451073"},{"issue":"4","key":"e_1_3_4_5_2","doi-asserted-by":"crossref","first-page":"844","DOI":"10.1145\/210332.210337","article-title":"Color-coding","volume":"42","author":"Alon Noga","year":"1995","unstructured":"Noga Alon, Raphael Yuster, and Uri Zwick. 1995. Color-coding. Journal of the ACM (JACM) 42, 4 (1995), 844\u2013856.","journal-title":"Journal of the ACM (JACM)"},{"key":"e_1_3_4_6_2","first-page":"605","volume-title":"Proceedings of the 39th Annual ACM Symposium on Theory of Computing, San Diego, California, USA, June 11\u201313, 2007","author":"Bhalgat Anand","year":"2007","unstructured":"Anand Bhalgat, Ramesh Hariharan, Telikepalli Kavitha, and Debmalya Panigrahi. 2007. An \u00d5(mn) Gomory-Hu tree construction algorithm for unweighted graphs. In Proceedings of the 39th Annual ACM Symposium on Theory of Computing, San Diego, California, USA, June 11\u201313, 2007, David S. Johnson and Uriel Feige (Eds.). ACM, 605\u2013614."},{"key":"e_1_3_4_7_2","first-page":"455","volume-title":"Proceedings of the 19th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2008, San Francisco, California, USA, January 20\u201322, 2008","author":"Bhalgat Anand","year":"2008","unstructured":"Anand Bhalgat, Ramesh Hariharan, Telikepalli Kavitha, and Debmalya Panigrahi. 2008. Fast edge splitting and Edmonds\u2019 arborescence construction for unweighted graphs. In Proceedings of the 19th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2008, San Francisco, California, USA, January 20\u201322, 2008, Shang-Hua Teng (Ed.). SIAM, 455\u2013464."},{"key":"e_1_3_4_8_2","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611977073.127"},{"key":"e_1_3_4_9_2","doi-asserted-by":"crossref","unstructured":"Ruoxu Cen Jason Li and Debmalya Panigrahi. Edge connectivity augmentation in near-linear time. In Proceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing (STOC 2022). 137\u2013150.","DOI":"10.1145\/3519935.3520038"},{"key":"e_1_3_4_10_2","series-title":"LIPIcs","first-page":"50:1\u201350:20","volume-title":"Proceedings of the 48th International Colloquium on Automata, Languages, and Programming, ICALP 2021, July 12\u201316, 2021, Glasgow, Scotland (Virtual Conference)","volume":"198","author":"Chekuri Chandra","year":"2021","unstructured":"Chandra Chekuri and Kent Quanrud. 2021. Isolating cuts, (Bi-)Submodularity, and faster algorithms for connectivity. In Proceedings of the 48th International Colloquium on Automata, Languages, and Programming, ICALP 2021, July 12\u201316, 2021, Glasgow, Scotland (Virtual Conference)(LIPIcs, Vol. 198), Nikhil Bansal, Emanuela Merelli, and James Worrell (Eds.). Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik, 50:1\u201350:20."},{"key":"e_1_3_4_11_2","first-page":"167","volume-title":"Proceedings of the 35th Annual ACM Symposium on Theory of Computing, June 9\u201311, 2003, San Diego, CA, USA","author":"Cole Richard","year":"2003","unstructured":"Richard Cole and Ramesh Hariharan. 2003. A fast algorithm for computing steiner edge connectivity. In Proceedings of the 35th Annual ACM Symposium on Theory of Computing, June 9\u201311, 2003, San Diego, CA, USA, Lawrence L. Larmore and Michel X. Goemans (Eds.). ACM, 167\u2013176."},{"key":"e_1_3_4_12_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-21275-3"},{"key":"e_1_3_4_13_2","volume-title":"Proceedings of the European Symposium on Algorithms","author":"Ding Matthew","year":"2024","unstructured":"Matthew Ding and Jason Li. 2024. Deterministic minimum steiner cut in maximum flow time. In Proceedings of the European Symposium on Algorithms."},{"key":"e_1_3_4_14_2","first-page":"716","volume-title":"Proceedings of the 26th Annual ACM Symposium on Theory of Computing, 23\u201325 May 1994, Montr\u00e9al, Qu\u00e9bec, Canada","author":"Dinitz Yefim","year":"1994","unstructured":"Yefim Dinitz and Alek Vainshtein. 1994. The connectivity carcass of a vertex subset in a graph and its incremental maintenance. In Proceedings of the 26th Annual ACM Symposium on Theory of Computing, 23\u201325 May 1994, Montr\u00e9al, Qu\u00e9bec, Canada, Frank Thomson Leighton and Michael T. Goodrich (Eds.). ACM, 716\u2013725."},{"key":"e_1_3_4_15_2","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.1995.1022"},{"issue":"5","key":"e_1_3_4_16_2","doi-asserted-by":"crossref","first-page":"783","DOI":"10.1145\/290179.290181","article-title":"Beyond the flow decomposition barrier","volume":"45","author":"Goldberg Andrew V.","year":"1998","unstructured":"Andrew V. Goldberg and Satish Rao. 1998. Beyond the flow decomposition barrier. Journal of the ACM (JACM) 45, 5 (1998), 783\u2013797.","journal-title":"Journal of the ACM (JACM)"},{"key":"e_1_3_4_17_2","doi-asserted-by":"publisher","DOI":"10.1145\/48014.61051"},{"issue":"4","key":"e_1_3_4_18_2","doi-asserted-by":"crossref","first-page":"551","DOI":"10.1137\/0109047","article-title":"Multi-terminal network flows","volume":"9","author":"Gomory Ralph E.","year":"1961","unstructured":"Ralph E. Gomory and Tien Chung Hu. 1961. Multi-terminal network flows. Journal of the Society for Industrial and Applied Mathematics 9, 4 (1961), 551\u2013570.","journal-title":"Journal of the Society for Industrial and Applied Mathematics"},{"key":"e_1_3_4_19_2","doi-asserted-by":"publisher","DOI":"10.5555\/139404.139439"},{"key":"e_1_3_4_20_2","first-page":"127","volume-title":"Proceedings of the 18th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2007, New Orleans, Louisiana, USA, January 7\u20139, 2007","author":"Hariharan Ramesh","year":"2007","unstructured":"Ramesh Hariharan, Telikepalli Kavitha, and Debmalya Panigrahi. 2007. Efficient algorithms for computing all low s-t edge connectivities and related problems. In Proceedings of the 18th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2007, New Orleans, Louisiana, USA, January 7\u20139, 2007, Nikhil Bansal, Kirk Pruhs, and Clifford Stein (Eds.). SIAM, 127\u2013136."},{"key":"e_1_3_4_21_2","doi-asserted-by":"crossref","first-page":"3089","DOI":"10.1137\/1.9781611977912.111","volume-title":"Proceedings of the 2024 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA\u201924)","author":"Henzinger Monika","year":"2024","unstructured":"Monika Henzinger, Jason Li, Satish Rao, and Di Wang. 2024. Deterministic near-linear time minimum cut in weighted graphs. In Proceedings of the 2024 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA\u201924). SIAM, 3089\u20133139."},{"key":"e_1_3_4_22_2","first-page":"1919","volume-title":"Proceedings of the 28th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2017, Barcelona, Spain, Hotel Porta Fira, January 16\u201319","author":"Henzinger Monika","year":"2017","unstructured":"Monika Henzinger, Satish Rao, and Di Wang. 2017. Local flow partitioning for faster edge connectivity. In Proceedings of the 28th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2017, Barcelona, Spain, Hotel Porta Fira, January 16\u201319. 1919\u20131938. DOI:10.1137\/1.9781611974782.125"},{"key":"e_1_3_4_23_2","first-page":"462","volume-title":"Proceedings of the 37th Annual Symposium on Foundations of Computer Science, FOCS \u201996, Burlington, Vermont, USA, 14\u201316 October, 1996","author":"Henzinger Monika Rauch","year":"1996","unstructured":"Monika Rauch Henzinger, Satish Rao, and Harold N. Gabow. 1996. Computing vertex connectivity: New bounds from old techniques. In Proceedings of the 37th Annual Symposium on Foundations of Computer Science, FOCS \u201996, Burlington, Vermont, USA, 14\u201316 October, 1996. IEEE Computer Society, 462\u2013471. DOI:10.1109\/SFCS.1996.548505"},{"key":"e_1_3_4_24_2","first-page":"21","volume-title":"Proceedings of the SODA","volume":"93","author":"Karger David R.","year":"1993","unstructured":"David R. Karger. 1993. Global min-cuts in RNC, and other ramifications of a simple min-cut algorithm.. In Proceedings of the SODA, Vol. 93. 21\u201330."},{"key":"e_1_3_4_25_2","doi-asserted-by":"publisher","DOI":"10.1145\/331605.331608"},{"issue":"4","key":"e_1_3_4_26_2","doi-asserted-by":"crossref","first-page":"601","DOI":"10.1145\/234533.234534","article-title":"A new approach to the minimum cut problem","volume":"43","author":"Karger David R.","year":"1996","unstructured":"David R. Karger and Clifford Stein. 1996. A new approach to the minimum cut problem. Journal of the ACM (JACM) 43, 4 (1996), 601\u2013640.","journal-title":"Journal of the ACM (JACM)"},{"issue":"1","key":"e_1_3_4_27_2","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1145\/3274663","article-title":"Deterministic edge connectivity in near-linear time","volume":"66","author":"Kawarabayashi Ken-ichi","year":"2018","unstructured":"Ken-ichi Kawarabayashi and Mikkel Thorup. 2018. Deterministic edge connectivity in near-linear time. Journal of the ACM (JACM) 66, 1 (2018), 1\u201350.","journal-title":"Journal of the ACM (JACM)"},{"key":"e_1_3_4_28_2","first-page":"317","volume-title":"Proceedings of the STOC\u201921: 53rd Annual ACM SIGACT Symposium on Theory of Computing, Virtual Event, Italy, June 21\u201325, 2021","author":"Li Jason","year":"2021","unstructured":"Jason Li, Danupon Nanongkai, Debmalya Panigrahi, Thatchaphol Saranurak, and Sorrachai Yingchareonthawornchai. 2021. Vertex connectivity in poly-logarithmic max-flows. In Proceedings of the STOC\u201921: 53rd Annual ACM SIGACT Symposium on Theory of Computing, Virtual Event, Italy, June 21\u201325, 2021, Samir Khuller and Virginia Vassilevska Williams (Eds.). ACM, 317\u2013329. DOI:10.1145\/3406325.3451088"},{"key":"e_1_3_4_29_2","first-page":"1738","volume-title":"Proceedings of the STOC \u201921: 53rd Annual ACM SIGACT Symposium on Theory of Computing, Virtual Event, Italy, June 21\u201325, 2021","author":"Li Jason","year":"2021","unstructured":"Jason Li and Debmalya Panigrahi. 2021. Approximate Gomory-Hu tree is faster than n\u20131 max-flows. In Proceedings of the STOC \u201921: 53rd Annual ACM SIGACT Symposium on Theory of Computing, Virtual Event, Italy, June 21\u201325, 2021, Samir Khuller and Virginia Vassilevska Williams (Eds.). ACM, 1738\u20131748. DOI:10.1145\/3406325.3451112"},{"key":"e_1_3_4_30_2","volume-title":"Proceedings of the Foundations of Computer Science (FOCS), 2021 IEEE 62nd Annual Symposium on","author":"Li Jason","year":"2021","unstructured":"Jason Li, Debmalya Panigrahi, and Thatchaphol Saranurak. 2021. A nearly optimal all-pairs min-cuts algorithm in simple graphs. In Proceedings of the Foundations of Computer Science (FOCS), 2021 IEEE 62nd Annual Symposium on."},{"key":"e_1_3_4_31_2","unstructured":"Jason Li and Thatchaphol Saranurak. 2021. Deterministic weighted expander decomposition in almost-linear time. arXiv:2106.01567. Retrieved from https:\/\/arxiv.org\/abs\/2106.01567 (2021)."},{"key":"e_1_3_4_32_2","article-title":"A note on isolating cut lemma for submodular function minimization","author":"Mukhopadhyay Sagnik","year":"2021","unstructured":"Sagnik Mukhopadhyay and Danupon Nanongkai. 2021. A note on isolating cut lemma for submodular function minimization. CoRR (2021). arXiv:2103.15724. Retrieved from https:\/\/arxiv.org\/abs\/2103.15724","journal-title":"CoRR"},{"issue":"1","key":"e_1_3_4_33_2","doi-asserted-by":"crossref","first-page":"54","DOI":"10.1137\/0405004","article-title":"Computing edge-connectivity in multigraphs and capacitated graphs","volume":"5","author":"Nagamochi Hiroshi","year":"1992","unstructured":"Hiroshi Nagamochi and Toshihide Ibaraki. 1992. Computing edge-connectivity in multigraphs and capacitated graphs. SIAM Journal on Discrete Mathematics 5, 1 (1992), 54\u201366.","journal-title":"SIAM Journal on Discrete Mathematics"},{"key":"e_1_3_4_34_2","doi-asserted-by":"publisher","DOI":"10.1007\/BF01758778"},{"key":"e_1_3_4_35_2","doi-asserted-by":"publisher","DOI":"10.1145\/263867.263872"},{"key":"e_1_3_4_36_2","doi-asserted-by":"crossref","first-page":"503","DOI":"10.1109\/FOCS57990.2023.00037","volume-title":"Proceedings of the 2023 IEEE 64th Annual Symposium on Foundations of Computer Science (FOCS\u201923)","author":"Brand Jan Van Den","year":"2023","unstructured":"Jan Van Den Brand, Li Chen, Richard Peng, Rasmus Kyng, Yang P. Liu, Maximilian Probst Gutenberg, Sushant Sachdeva, and Aaron Sidford. 2023. A deterministic almost-linear time algorithm for minimum-cost flow. In Proceedings of the 2023 IEEE 64th Annual Symposium on Foundations of Computer Science (FOCS\u201923). IEEE, 503\u2013514."},{"key":"e_1_3_4_37_2","unstructured":"Tianyi Zhang. 2022. Faster cut-equivalent trees in simple graphs. Proceedings of the 49th EATCS International Colloquium on Automata Languages and Programming (ICALP 2022). 109:1\u2013109:18."}],"container-title":["Journal of the ACM"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3744737","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,7,24]],"date-time":"2025-07-24T13:52:28Z","timestamp":1753365148000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3744737"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,7,24]]},"references-count":36,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2025,8,31]]}},"alternative-id":["10.1145\/3744737"],"URL":"https:\/\/doi.org\/10.1145\/3744737","relation":{},"ISSN":["0004-5411","1557-735X"],"issn-type":[{"value":"0004-5411","type":"print"},{"value":"1557-735X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2025,7,24]]},"assertion":[{"value":"2022-05-27","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2025-05-26","order":2,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2025-07-24","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}