{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,8,2]],"date-time":"2025-08-02T18:31:16Z","timestamp":1754159476977,"version":"3.41.2"},"reference-count":31,"publisher":"Association for Computing Machinery (ACM)","issue":"4","funder":[{"name":"European Research Council","award":["715672 and 759557"],"award-info":[{"award-number":["715672 and 759557"]}]},{"DOI":"10.13039\/501100004359","name":"Swedish Research Council","doi-asserted-by":"crossref","award":["2019-05622"],"award-info":[{"award-number":["2019-05622"]}],"id":[{"id":"10.13039\/501100004359","id-type":"DOI","asserted-by":"crossref"}]},{"name":"NSF","award":["CCF 1750140 and CCF 1955703"],"award-info":[{"award-number":["CCF 1750140 and CCF 1955703"]}]}],"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            The vertex connectivity of an\n            <jats:italic toggle=\"yes\">m<\/jats:italic>\n            -edge\n            <jats:italic toggle=\"yes\">n<\/jats:italic>\n            -vertex undirected graph is the smallest number of vertices whose removal disconnects the graph or leaves only a singleton vertex. In 1974, Aho Hopcroft and Ullman asked if vertex connectivity can be computed in linear time. Despite the substantial effort in the past five decades, the best-known running time is\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            by Henzinger-Rao-Gabow (FOCS 1996). Indeed, no algorithm with an\n            <jats:italic toggle=\"yes\">o<\/jats:italic>\n            (\n            <jats:italic toggle=\"yes\">mn<\/jats:italic>\n            ) running time is known\n            <jats:italic toggle=\"yes\">even if we assume a linear-time max-flow algorithm.<\/jats:italic>\n          <\/jats:p>\n          <jats:p>\n            In this article, we give an affirmative answer to this long-standing open problem (up to a sub-polynomial factor). We present a randomized reduction from the vertex connectivity problem to the max-flow problem which incurs only a poly-logarithmic overhead in runtime. Using this reduction, we can solve vertex connectivity in almost linear time by using the celebrated almost-linear-time max-flow algorithms by Chen-Kyng-Liu-Peng-Probst Gutenberg-Sachdeva (FOCS 2022) and Brand-Chen-Kyng-Liu-Peng-Probst Gutenberg-Sachdeva-Sidford (FOCS 2023). Using our new techniques, we also obtain an algorithm for directed vertex connectivity with a running time of\n            <jats:italic toggle=\"yes\">n<\/jats:italic>\n            <jats:sup>\n              2 +\n              <jats:italic toggle=\"yes\">o<\/jats:italic>\n              (1)\n            <\/jats:sup>\n            time which improves the best-known 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            by Henzinger-Rao-Gabow (FOCS 1996).\n          <\/jats:p>","DOI":"10.1145\/3743670","type":"journal-article","created":{"date-parts":[[2025,6,14]],"date-time":"2025-06-14T06:49:34Z","timestamp":1749883774000},"page":"1-34","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":0,"title":["Vertex Connectivity in Poly-logarithmic Max-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-4468-2675","authenticated-orcid":false,"given":"Danupon","family":"Nanongkai","sequence":"additional","affiliation":[{"name":"KTH Royal Institute of Technology","place":["Stockholm, Sweden"]},{"name":"University of Copenhagen","place":["Stockholm, Sweden"]},{"name":"Theoretical Computer Science, Max-Planck-Institut fur Informatik","place":["Stockholm, Sweden"]}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-1799-6660","authenticated-orcid":false,"given":"Debmalya","family":"Panigrahi","sequence":"additional","affiliation":[{"name":"Duke University","place":["Durham, United States"]}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-8386-7168","authenticated-orcid":false,"given":"Thatchaphol","family":"Saranurak","sequence":"additional","affiliation":[{"name":"University of Michigan","place":["Ann Arbor, United States"]}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-7169-0163","authenticated-orcid":false,"given":"Sorrachai","family":"Yingchareonthawornchai","sequence":"additional","affiliation":[{"name":"Computer Science, Aalto University","place":["Aalto, Finland"]},{"name":"Institute for Theoretical Studies, ETH Zurich","place":["Aalto, Finland"]}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2025,7,25]]},"reference":[{"key":"e_1_3_3_2_2","doi-asserted-by":"publisher","DOI":"10.5555\/578775"},{"key":"e_1_3_3_3_2","doi-asserted-by":"publisher","unstructured":"Josh Alman and Virginia Vassilevska Williams. 2024. A refined laser method and faster matrix multiplication. TheoretiCS 3 Article 21 (Sep 2024). 10.46298\/theoretics.24.21","DOI":"10.46298\/theoretics.24.21"},{"key":"e_1_3_3_4_2","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.1997.1545"},{"key":"e_1_3_3_5_2","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(82)90046-1"},{"key":"e_1_3_3_6_2","first-page":"156","volume-title":"Proceedings of the PODC","author":"Censor-Hillel Keren","year":"2014","unstructured":"Keren Censor-Hillel, Mohsen Ghaffari, and Fabian Kuhn. 2014. Distributed connectivity decomposition. In Proceedings of the PODC. ACM, 156\u2013165."},{"key":"e_1_3_3_7_2","first-page":"612","volume-title":"Proceedings of the FOCS","author":"Chen Li","year":"2022","unstructured":"Li Chen, Rasmus Kyng, Yang P. Liu, Richard Peng, Maximilian Probst Gutenberg, and Sushant Sachdeva. 2022. Maximum flow and minimum-cost flow in almost-linear time. In Proceedings of the FOCS. IEEE, 612\u2013623."},{"key":"e_1_3_3_8_2","first-page":"391","volume-title":"Proceedings of the STOC","author":"Cheriyan Joseph","year":"1991","unstructured":"Joseph Cheriyan and Ramakrishna Thurimella. 1991. Algorithms for parallel k-Vertex connectivity and sparse certificates (Extended Abstract). In Proceedings of the STOC. ACM, 391\u2013401."},{"issue":"3","key":"e_1_3_3_9_2","doi-asserted-by":"crossref","first-page":"315","DOI":"10.1007\/s10619-013-7131-9","article-title":"A unifying framework for  \\(\\ell _0\\) -sampling algorithms","volume":"32","author":"Cormode Graham","year":"2014","unstructured":"Graham Cormode and Donatella Firmani. 2014. A unifying framework for \\(\\ell _0\\) -sampling algorithms. Distributed Parallel Databases 32, 3 (2014), 315\u2013335.","journal-title":"Distributed Parallel Databases"},{"key":"e_1_3_3_10_2","unstructured":"Yefim A. Dinitz. 1970. An algorithm for the solution of the problem of maximal flow in a network with power estimation. In Doklady Akademii Nauk Vol. 194. Russian Academy of Sciences 754\u2013757."},{"key":"e_1_3_3_11_2","doi-asserted-by":"publisher","DOI":"10.1137\/0204034"},{"key":"e_1_3_3_12_2","doi-asserted-by":"publisher","DOI":"10.1137\/0204043"},{"key":"e_1_3_3_13_2","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611975994.126"},{"key":"e_1_3_3_14_2","doi-asserted-by":"publisher","DOI":"10.1145\/1183907.1183912"},{"key":"e_1_3_3_15_2","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"738","DOI":"10.1007\/978-3-642-14165-2_62","volume-title":"Proceedings of the ICALP (1)","volume":"6198","author":"Georgiadis Loukas","year":"2010","unstructured":"Loukas Georgiadis. 2010. Testing 2-Vertex connectivity and computing pairs of vertex-disjoint s-t paths in digraphs. In Proceedings of the ICALP (1)(Lecture Notes in Computer Science, Vol. 6198). Springer, 738\u2013749."},{"key":"e_1_3_3_16_2","doi-asserted-by":"publisher","DOI":"10.1145\/48014.61051"},{"key":"e_1_3_3_17_2","doi-asserted-by":"publisher","DOI":"10.1006\/jagm.1994.1043"},{"key":"e_1_3_3_18_2","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611974782.125"},{"key":"e_1_3_3_19_2","doi-asserted-by":"publisher","DOI":"10.1006\/jagm.1999.1055"},{"key":"e_1_3_3_20_2","doi-asserted-by":"publisher","DOI":"10.1137\/0202012"},{"key":"e_1_3_3_21_2","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(91)90004-O"},{"key":"e_1_3_3_22_2","doi-asserted-by":"publisher","DOI":"10.1109\/TCT.1969.1082941"},{"key":"e_1_3_3_23_2","volume-title":"Proceedings of the 61st IEEE Annual Symposium on Foundations of Computer Science, FOCS 2020","author":"Li Jason","year":"2020","unstructured":"Jason Li and Debmalya Panigrahi. 2020. Deterministic min-cut in poly-logarithmic max-flows. In Proceedings of the 61st IEEE Annual Symposium on Foundations of Computer Science, FOCS 2020. IEEE Computer Society."},{"key":"e_1_3_3_24_2","doi-asserted-by":"publisher","DOI":"10.1007\/BF02122557"},{"key":"e_1_3_3_25_2","doi-asserted-by":"publisher","DOI":"10.1007\/BF01758778"},{"key":"e_1_3_3_26_2","doi-asserted-by":"crossref","unstructured":"Yonggang Jiang Chaitanya Nalam Thatchaphol Saranurak and Sorrachai Yingchareonthawornchai. 2025. Deterministic vertex connectivity via common-neighborhood clustering and pseudorandomness. In Proceedings of the 57th Annual ACM Symposium on Theory of Computing. 2293\u20132304.","DOI":"10.1145\/3717823.3718304"},{"key":"e_1_3_3_27_2","doi-asserted-by":"publisher","DOI":"10.1145\/3313276.3316394"},{"key":"e_1_3_3_28_2","first-page":"136","article-title":"An algorithm for finding the edge connectivity of graphs","volume":"2","author":"Podderyugin V. D.","year":"1973","unstructured":"V. D. Podderyugin. 1973. An algorithm for finding the edge connectivity of graphs. Vopr. Kibern 2 (1973), 136.","journal-title":"Vopr. Kibern"},{"key":"e_1_3_3_29_2","first-page":"789","volume-title":"FOCS","author":"Saranurak Thatchaphol","year":"2022","unstructured":"Thatchaphol Saranurak and Sorrachai Yingchareonthawornchai. 2022. Deterministic small vertex connectivity in almost linear time. In Proceedings of the FOCS. IEEE, 789\u2013800."},{"key":"e_1_3_3_30_2","doi-asserted-by":"publisher","DOI":"10.1137\/0201010"},{"key":"e_1_3_3_31_2","doi-asserted-by":"crossref","unstructured":"Jan Van Den Brand Li Chen Rasmus Kyng Yang P. Liu Richard Peng Maximilian Probst Gutenberg Sushant Sachdeva and Aaron Sidford. 2023. A deterministic almost-linear time algorithm for minimum-cost flow. In 2023 IEEE 64th Annual Symposium on Foundations of Computer Science (FOCS). IEEE 503\u2013514.","DOI":"10.1109\/FOCS57990.2023.00037"},{"key":"e_1_3_3_32_2","first-page":"3792","volume-title":"Proceedings of the SODA","author":"Williams Virginia Vassilevska","year":"2024","unstructured":"Virginia Vassilevska Williams, Yinzhan Xu, Zixuan Xu, and Renfei Zhou. 2024. New bounds for matrix multiplication: from alpha to omega. In Proceedings of the SODA. SIAM, 3792\u20133835."}],"container-title":["Journal of the ACM"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3743670","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,7,25]],"date-time":"2025-07-25T12:11:49Z","timestamp":1753445509000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3743670"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,7,25]]},"references-count":31,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2025,8,31]]}},"alternative-id":["10.1145\/3743670"],"URL":"https:\/\/doi.org\/10.1145\/3743670","relation":{},"ISSN":["0004-5411","1557-735X"],"issn-type":[{"type":"print","value":"0004-5411"},{"type":"electronic","value":"1557-735X"}],"subject":[],"published":{"date-parts":[[2025,7,25]]},"assertion":[{"value":"2021-11-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-25","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}