{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,13]],"date-time":"2026-02-13T14:45:52Z","timestamp":1770993952969,"version":"3.50.1"},"reference-count":15,"publisher":"Association for Computing Machinery (ACM)","issue":"1","license":[{"start":{"date-parts":[[2021,11,29]],"date-time":"2021-11-29T00:00:00Z","timestamp":1638144000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["J. ACM"],"published-print":{"date-parts":[[2022,2,28]]},"abstract":"<jats:p>\n            In the\n            <jats:italic>k<\/jats:italic>\n            -cut problem, we want to find the lowest-weight set of edges whose deletion breaks a given (multi)graph into\n            <jats:italic>k<\/jats:italic>\n            connected components. Algorithms of Karger and Stein can solve this in roughly\n            <jats:italic>O<\/jats:italic>\n            (\n            <jats:italic>n<\/jats:italic>\n            <jats:italic>\n              <jats:sup>2k<\/jats:sup>\n            <\/jats:italic>\n            ) time. However, lower bounds from conjectures about the\n            <jats:italic>k<\/jats:italic>\n            -clique problem imply that \u03a9 (\n            <jats:italic>n<\/jats:italic>\n            <jats:sup>\n              (1-\n              <jats:italic>o<\/jats:italic>\n              (1))\n              <jats:italic>k<\/jats:italic>\n            <\/jats:sup>\n            ) time is likely needed. Recent results of Gupta, Lee, and Li have given new algorithms for general\n            <jats:italic>k<\/jats:italic>\n            -cut in\n            <jats:italic>n<\/jats:italic>\n            <jats:sup>1.98k + O(1)<\/jats:sup>\n            time, as well as specialized algorithms with better performance for certain classes of graphs (e.g., for small integer edge weights).\n          <\/jats:p>\n          <jats:p>\n            In this work, we resolve the problem for general graphs. We show that the Contraction Algorithm of Karger outputs any fixed\n            <jats:italic>k<\/jats:italic>\n            -cut of weight \u03b1 \u03bb\n            <jats:sub>k<\/jats:sub>\n            with probability \u03a9\n            <jats:sub>k<\/jats:sub>\n            (\n            <jats:italic>n<\/jats:italic>\n            -\n            <jats:sup>\n              \u03b1\n              <jats:italic>k<\/jats:italic>\n            <\/jats:sup>\n            ), where \u03bb\n            <jats:sub>k<\/jats:sub>\n            denotes the minimum\n            <jats:italic>k<\/jats:italic>\n            -cut weight. This also gives an extremal bound of\n            <jats:italic>\n              O\n              <jats:sub>k<\/jats:sub>\n            <\/jats:italic>\n            (\n            <jats:italic>\n              n\n              <jats:sup>k<\/jats:sup>\n            <\/jats:italic>\n            ) on the number of minimum\n            <jats:italic>k<\/jats:italic>\n            -cuts and an algorithm to compute \u03bb\n            <jats:italic>k<\/jats:italic>\n            with roughly\n            <jats:italic>\n              n\n              <jats:sup>k<\/jats:sup>\n            <\/jats:italic>\n            polylog(\n            <jats:italic>n<\/jats:italic>\n            ) runtime. Both are tight up to lower-order factors, with the algorithmic lower bound assuming hardness of max-weight\n            <jats:italic>k<\/jats:italic>\n            -clique.\n          <\/jats:p>\n          <jats:p>\n            The first main ingredient in our result is an extremal bound on the number of cuts of weight less than 2 \u03bb\n            <jats:sub>\n              <jats:italic>k<\/jats:italic>\n            <\/jats:sub>\n            \/\n            <jats:italic>k<\/jats:italic>\n            , using the Sunflower lemma. The second ingredient is a fine-grained analysis of how the graph shrinks\u2014and how the average degree evolves\u2014in the Karger process.\n          <\/jats:p>","DOI":"10.1145\/3478018","type":"journal-article","created":{"date-parts":[[2021,11,30]],"date-time":"2021-11-30T01:58:53Z","timestamp":1638237533000},"page":"1-18","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":4,"title":["Optimal Bounds for the\n            <i>k<\/i>\n            -cut Problem"],"prefix":"10.1145","volume":"69","author":[{"given":"Anupam","family":"Gupta","sequence":"first","affiliation":[{"name":"Carnegie Mellon University, Pittsburgh, PA, USA"}]},{"given":"David G.","family":"Harris","sequence":"additional","affiliation":[{"name":"University of Maryland, College Park, MD, USA"}]},{"given":"Euiwoong","family":"Lee","sequence":"additional","affiliation":[{"name":"University of Michigan, Ann Arbor, MI, USA"}]},{"given":"Jason","family":"Li","sequence":"additional","affiliation":[{"name":"Carnegie Mellon University, Pittsburgh, PA, USA"}]}],"member":"320","published-online":{"date-parts":[[2021,11,29]]},"reference":[{"key":"e_1_3_4_2_2","doi-asserted-by":"publisher","DOI":"10.1145\/3357713.3384234"},{"key":"e_1_3_4_3_2","doi-asserted-by":"publisher","DOI":"10.1137\/19M1299359"},{"key":"e_1_3_4_4_2","doi-asserted-by":"publisher","DOI":"10.1112\/jlms\/s1-35.1.85"},{"key":"e_1_3_4_5_2","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1988.21960"},{"key":"e_1_3_4_6_2","doi-asserted-by":"publisher","DOI":"10.5555\/182072.182075"},{"key":"e_1_3_4_7_2","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2018.00020"},{"key":"e_1_3_4_8_2","doi-asserted-by":"publisher","DOI":"10.1145\/3313276.3316395"},{"key":"e_1_3_4_9_2","doi-asserted-by":"publisher","DOI":"10.1145\/3357713.3384285"},{"key":"e_1_3_4_10_2","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.20724"},{"key":"e_1_3_4_11_2","doi-asserted-by":"publisher","DOI":"10.1137\/050631616"},{"key":"e_1_3_4_12_2","doi-asserted-by":"publisher","DOI":"10.5555\/313559.313605"},{"key":"e_1_3_4_13_2","doi-asserted-by":"publisher","DOI":"10.1145\/234533.234534"},{"key":"e_1_3_4_14_2","doi-asserted-by":"publisher","DOI":"10.1145\/3274663"},{"key":"e_1_3_4_15_2","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2019.00068"},{"key":"e_1_3_4_16_2","doi-asserted-by":"publisher","DOI":"10.1145\/1374376.1374402"}],"container-title":["Journal of the ACM"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3478018","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3478018","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T19:31:32Z","timestamp":1750188692000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3478018"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,11,29]]},"references-count":15,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2022,2,28]]}},"alternative-id":["10.1145\/3478018"],"URL":"https:\/\/doi.org\/10.1145\/3478018","relation":{},"ISSN":["0004-5411","1557-735X"],"issn-type":[{"value":"0004-5411","type":"print"},{"value":"1557-735X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2021,11,29]]},"assertion":[{"value":"2020-05-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2021-07-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2021-11-29","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}