{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,13]],"date-time":"2026-05-13T03:43:08Z","timestamp":1778643788645,"version":"3.51.4"},"reference-count":32,"publisher":"Association for Computing Machinery (ACM)","issue":"2","license":[{"start":{"date-parts":[[2023,4,15]],"date-time":"2023-04-15T00:00:00Z","timestamp":1681516800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"NSF","award":["CCF-1527084"],"award-info":[{"award-number":["CCF-1527084"]}]},{"name":"NSF","award":["CCF-1527084, CCF-1535972"],"award-info":[{"award-number":["CCF-1527084, CCF-1535972"]}]},{"name":"NSF CAREER","award":["CCF-1750140"],"award-info":[{"award-number":["CCF-1750140"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Algorithms"],"published-print":{"date-parts":[[2023,4,30]]},"abstract":"<jats:p>\n            On hypergraphs with\n            <jats:italic>m<\/jats:italic>\n            hyperedges and\n            <jats:italic>n<\/jats:italic>\n            vertices, where\n            <jats:italic>p<\/jats:italic>\n            denotes the total size of the hyperedges, we provide the following results:\n            <jats:list list-type=\"bullet\">\n              <jats:list-item>\n                <jats:p>\n                  We give an algorithm that runs in\n                  <jats:inline-formula content-type=\"math\/tex\">\n                    <jats:tex-math notation=\"LaTeX\" version=\"MathJax\">\\(\\widetilde{O}(mn^{2k-2})\\)<\/jats:tex-math>\n                  <\/jats:inline-formula>\n                  time for finding a minimum\n                  <jats:italic>k<\/jats:italic>\n                  -cut in hypergraphs of arbitrary rank. This algorithm betters the previous best running time for the minimum\n                  <jats:italic>k<\/jats:italic>\n                  -cut problem, for\n                  <jats:italic>k<\/jats:italic>\n                  &gt; 2.\n                <\/jats:p>\n              <\/jats:list-item>\n              <jats:list-item>\n                <jats:p>\n                  We give an algorithm that runs in\n                  <jats:inline-formula content-type=\"math\/tex\">\n                    <jats:tex-math notation=\"LaTeX\" version=\"MathJax\">\\(\\widetilde{O}(n^{\\max \\lbrace r,2k-2\\rbrace })\\)<\/jats:tex-math>\n                  <\/jats:inline-formula>\n                  time for finding a minimum\n                  <jats:italic>k<\/jats:italic>\n                  -cut in hypergraphs of constant rank\n                  <jats:italic>r<\/jats:italic>\n                  . This algorithm betters the previous best running times for both the minimum cut and minimum\n                  <jats:italic>k<\/jats:italic>\n                  -cut problems for dense hypergraphs.\n                <\/jats:p>\n              <\/jats:list-item>\n            <\/jats:list>\n            Both of our algorithms are Monte Carlo, i.e., they return a minimum\n            <jats:italic>k<\/jats:italic>\n            -cut (or minimum cut) with high probability. These algorithms are obtained as instantiations of a generic\n            <jats:italic>branching randomized contraction<\/jats:italic>\n            technique on hypergraphs, which extends the celebrated work of Karger and Stein on recursive contractions in graphs. Our techniques and results also extend to the problems of minimum hedge-cut and minimum hedge-\n            <jats:italic>k<\/jats:italic>\n            -cut on hedgegraphs, which generalize hypergraphs.\n          <\/jats:p>","DOI":"10.1145\/3570162","type":"journal-article","created":{"date-parts":[[2022,10,29]],"date-time":"2022-10-29T12:17:45Z","timestamp":1667045865000},"page":"1-22","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":7,"title":["Minimum Cut and Minimum\n            <i>k<\/i>\n            -Cut in Hypergraphs via Branching Contractions"],"prefix":"10.1145","volume":"19","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-2446-8594","authenticated-orcid":false,"given":"Kyle","family":"Fox","sequence":"first","affiliation":[{"name":"The University of Texas at Dallas, Dallas, USA"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-1799-6660","authenticated-orcid":false,"given":"Debmalya","family":"Panigrahi","sequence":"additional","affiliation":[{"name":"Duke University, Durham, USA"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-7256-9843","authenticated-orcid":false,"given":"Fred","family":"Zhang","sequence":"additional","affiliation":[{"name":"UC Berkeley, Berkeley, USA"}]}],"member":"320","published-online":{"date-parts":[[2023,4,15]]},"reference":[{"key":"e_1_3_3_2_2","doi-asserted-by":"crossref","first-page":"70","DOI":"10.1007\/978-3-031-06901-7_6","volume-title":"Proceedings of the International Conference on Integer Programming and Combinatorial Optimization (IPCO\u201922)","author":"Beideman Calvin","year":"2022","unstructured":"Calvin Beideman, Karthekeyan Chandrasekaran, Sagnik Mukhopadhyay, and Danupon Nanongkai. 2022. Faster connectivity in low-rank hypergraphs via expander decomposition. In Proceedings of the International Conference on Integer Programming and Combinatorial Optimization (IPCO\u201922). 70\u201383."},{"key":"e_1_3_3_3_2","first-page":"16:1\u201316:18","volume-title":"Proceedings of the 49th International Colloquium on Automata, Languages, and Programming (ICALP\u201922)","volume":"229","author":"Beideman Calvin","year":"2022","unstructured":"Calvin Beideman, Karthekeyan Chandrasekaran, and Weihang Wang. 2022. Counting and enumerating optimum cut sets for hypergraph k-partitioning problems for fixed k. In Proceedings of the 49th International Colloquium on Automata, Languages, and Programming (ICALP\u201922), Vol. 229. 16:1\u201316:18."},{"key":"e_1_3_3_4_2","first-page":"2208","volume-title":"Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms (SODA\u201922)","author":"Beideman Calvin","year":"2022","unstructured":"Calvin Beideman, Karthekeyan Chandrasekaran, and Weihang Wang. 2022. Deterministic enumeration of all minimum k-cut-sets in hypergraphs for fixed k. In Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms (SODA\u201922). 2208\u20132228."},{"key":"e_1_3_3_5_2","first-page":"810","volume-title":"Proceedings of the IEEE 61st Annual Symposium on Foundations of Computer Science (FOCS\u201920)","author":"Chandrasekaran Karthekeyan","year":"2020","unstructured":"Karthekeyan Chandrasekaran and Chandra Chekuri. 2020. Hypergraph k-cut for fixed k in deterministic polynomial time. In Proceedings of the IEEE 61st Annual Symposium on Foundations of Computer Science (FOCS\u201920). IEEE, 810\u2013821."},{"key":"e_1_3_3_6_2","first-page":"1026","volume-title":"Proceedings of the ACM-SIAM Symposium on Discrete Algorithms (SODA\u201921)","author":"Chandrasekaran Karthekeyan","year":"2021","unstructured":"Karthekeyan Chandrasekaran and Chandra Chekuri. 2021. Min-max partitioning of hypergraphs and symmetric submodular functions. In Proceedings of the ACM-SIAM Symposium on Discrete Algorithms (SODA\u201921). SIAM, 1026\u20131038."},{"key":"e_1_3_3_7_2","first-page":"1426","volume-title":"Proceedings of the 29th Annual ACM\/SIGACT-SIAM Symposium on Discrete Algorithms (SODA\u201918)","author":"Chandrasekaran Karthekeyan","year":"2018","unstructured":"Karthekeyan Chandrasekaran, Chao Xu, and Xilin Yu. 2018. Hypergraph k-Cut in randomized polynomial time. In Proceedings of the 29th Annual ACM\/SIGACT-SIAM Symposium on Discrete Algorithms (SODA\u201918). 1426\u20131438."},{"key":"e_1_3_3_8_2","volume-title":"Proceedings of the 48th International Colloquium on Automata, Languages, and Programming (ICALP\u201921)","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\u201921). Schloss Dagstuhl-Leibniz-Zentrum f\u00fcr Informatik."},{"key":"e_1_3_3_9_2","volume-title":"Proceedings of the 2nd Symposium on Simplicity in Algorithms.","author":"Chekuri Chandra","year":"2019","unstructured":"Chandra Chekuri, Kent Quanrud, and Chao Xu. 2019. LP relaxation and tree packing for minimum k-cuts. In Proceedings of the 2nd Symposium on Simplicity in Algorithms."},{"key":"e_1_3_3_10_2","volume-title":"Proceedings of the 28th Annual ACM\/SIGACT-SIAM Symposium on Discrete Algorithms (SODA\u201917).","author":"Chekuri Chandra","year":"2017","unstructured":"Chandra Chekuri and Chao Xu. 2017. Computing minimum cuts in hypergraphs. In Proceedings of the 28th Annual ACM\/SIGACT-SIAM Symposium on Discrete Algorithms (SODA\u201917)."},{"key":"e_1_3_3_11_2","first-page":"881","volume-title":"Proceedings of the 30th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA\u201919)","author":"Fox Kyle","year":"2019","unstructured":"Kyle Fox, Debmalya Panigrahi, and Fred Zhang. 2019. Minimum cut and minimum k-cut in hypergraphs via branching contractions. In Proceedings of the 30th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA\u201919). 881\u2013896."},{"key":"e_1_3_3_12_2","doi-asserted-by":"publisher","DOI":"10.1145\/10.1016\/j.disopt.2013.10.002"},{"key":"e_1_3_3_13_2","volume-title":"Proceedings of the 28th Annual ACM\/SIGACT-SIAM Symposium on Discrete Algorithms (SODA\u201917)","author":"Ghaffari Mohsen","year":"2017","unstructured":"Mohsen Ghaffari, David Karger, and Debmalya Panigrahi. 2017. Random contractions and sampling for hypergraph and hedge connectivity. In Proceedings of the 28th Annual ACM\/SIGACT-SIAM Symposium on Discrete Algorithms (SODA\u201917)."},{"key":"e_1_3_3_14_2","doi-asserted-by":"publisher","DOI":"10.5555\/2797333.2797336"},{"key":"e_1_3_3_15_2","first-page":"113","volume-title":"Proceedings of the IEEE 59th Annual Symposium on Foundations of Computer Science (FOCS\u201918)","author":"Gupta Anupam","year":"2018","unstructured":"Anupam Gupta, Euiwoong Lee, and Jason Li. 2018. Faster exact and approximate algorithms for k-Cut. In Proceedings of the IEEE 59th Annual Symposium on Foundations of Computer Science (FOCS\u201918). IEEE, 113\u2013123."},{"key":"e_1_3_3_16_2","doi-asserted-by":"publisher","DOI":"10.1145\/3357713.3384285"},{"key":"e_1_3_3_17_2","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-001-0070-2"},{"key":"e_1_3_3_18_2","doi-asserted-by":"publisher","DOI":"10.1137\/050631616"},{"key":"e_1_3_3_19_2","first-page":"21","volume-title":"Proceedings of the 4th Annual ACM\/SIGACT-SIAM Symposium on Discrete Algorithms (SODA\u201993)","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 4th Annual ACM\/SIGACT-SIAM Symposium on Discrete Algorithms (SODA\u201993). 21\u201330."},{"key":"e_1_3_3_20_2","doi-asserted-by":"publisher","DOI":"10.1145\/331605.331608"},{"key":"e_1_3_3_21_2","doi-asserted-by":"publisher","DOI":"10.1145\/234533.234534"},{"key":"e_1_3_3_22_2","doi-asserted-by":"crossref","first-page":"68","DOI":"10.1137\/1.9781611976496.7","volume-title":"Proceedings of the Symposium on Simplicity in Algorithms (SOSA)","author":"Karger David R.","year":"2021","unstructured":"David R. Karger and David P. Williamson. 2021. Recursive random contraction revisited. In Proceedings of the Symposium on Simplicity in Algorithms (SOSA). 68\u201373."},{"key":"e_1_3_3_23_2","first-page":"665","volume-title":"Proceedings of the 47th Annual ACM Symposium on Theory of Computing (STOC\u201915)","author":"Kawarabayashi Ken-ichi","year":"2015","unstructured":"Ken-ichi Kawarabayashi and Mikkel Thorup. 2015. Deterministic global minimum cut of a simple graph in near-linear time. In Proceedings of the 47th Annual ACM Symposium on Theory of Computing (STOC\u201915). 665\u2013674."},{"key":"e_1_3_3_24_2","volume-title":"A Simple Hypergraph Min Cut Algorithm","author":"Klimmek Regina","year":"1996","unstructured":"Regina Klimmek and Frank Wagner. 1996. A Simple Hypergraph Min Cut Algorithm. Technical Report B 96-02. Bericht FU Berlin Fachbereich Mathematik und Informatik. Retrieved from http:\/\/edocs.fu-berlin.de\/docs\/servlets\/MCRFileNodeServlet\/FUDOCS_derivate_000000000297\/1996_02.pdf."},{"key":"e_1_3_3_25_2","first-page":"367","volume-title":"Proceedings of the 6th Conference on Innovations in Theoretical Computer Science (ITCS\u201915)","author":"Kogan Dmitry","year":"2015","unstructured":"Dmitry Kogan and Robert Krauthgamer. 2015. Sketching cuts in graphs and hypergraphs. In Proceedings of the 6th Conference on Innovations in Theoretical Computer Science (ITCS\u201915). 367\u2013376."},{"key":"e_1_3_3_26_2","doi-asserted-by":"publisher","DOI":"10.1016\/S0167-9260(00)00008-0"},{"key":"e_1_3_3_27_2","doi-asserted-by":"publisher","DOI":"10.1137\/0405004"},{"key":"e_1_3_3_28_2","doi-asserted-by":"publisher","DOI":"10.1007\/BF01758778"},{"key":"e_1_3_3_29_2","doi-asserted-by":"publisher","DOI":"10.1007\/BF01585863"},{"key":"e_1_3_3_30_2","doi-asserted-by":"publisher","DOI":"10.1145\/263867.263872"},{"key":"e_1_3_3_31_2","doi-asserted-by":"publisher","DOI":"10.1145\/1374376.1374402"},{"key":"e_1_3_3_32_2","doi-asserted-by":"crossref","first-page":"208","DOI":"10.1007\/978-3-540-92182-0_21","volume-title":"Proceedings of the International Symposium on Algorithms and Computation","author":"Xiao Mingyu","year":"2008","unstructured":"Mingyu Xiao. 2008. An improved divide-and-conquer algorithm for finding all minimum k-way cuts. In Proceedings of the International Symposium on Algorithms and Computation. Springer, 208\u2013219."},{"key":"e_1_3_3_33_2","doi-asserted-by":"publisher","DOI":"10.1145\/10.1016\/j.ipl.2010.05.003"}],"container-title":["ACM Transactions on Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3570162","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3570162","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T17:49:37Z","timestamp":1750182577000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3570162"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,4,15]]},"references-count":32,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2023,4,30]]}},"alternative-id":["10.1145\/3570162"],"URL":"https:\/\/doi.org\/10.1145\/3570162","relation":{},"ISSN":["1549-6325","1549-6333"],"issn-type":[{"value":"1549-6325","type":"print"},{"value":"1549-6333","type":"electronic"}],"subject":[],"published":{"date-parts":[[2023,4,15]]},"assertion":[{"value":"2022-01-05","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2022-10-26","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2023-04-15","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}