{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,7]],"date-time":"2026-04-07T14:57:17Z","timestamp":1775573837470,"version":"3.50.1"},"reference-count":35,"publisher":"Association for Computing Machinery (ACM)","issue":"2","funder":[{"name":"European Research Council","award":["714704"],"award-info":[{"award-number":["714704"]}]},{"name":"Independent Research Fund Denmark","award":["2098-00012B"],"award-info":[{"award-number":["2098-00012B"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Algorithms"],"published-print":{"date-parts":[[2026,4,30]]},"abstract":"<jats:p>\n                    We study a generalization of the classic\n                    <jats:sc>Global Min-Cut<\/jats:sc>\n                    problem, called\n                    <jats:sc>Global Label Min-Cut<\/jats:sc>\n                    (or sometimes\n                    <jats:sc>Global Hedge Min-Cut<\/jats:sc>\n                    ): the edges of the input (multi)graph are labeled (or partitioned into color classes or hedges), and removing all edges of the same label (color or from the same hedge) costs one. The problem asks to disconnect the graph at minimum cost.\n                  <\/jats:p>\n                  <jats:p>\n                    While the\n                    <jats:inline-formula content-type=\"math\/tex\">\n                      <jats:tex-math notation=\"LaTeX\" version=\"MathJax\">\\(st\\)<\/jats:tex-math>\n                    <\/jats:inline-formula>\n                    -cut version of the problem is known to be\n                    <jats:inline-formula content-type=\"math\/tex\">\n                      <jats:tex-math notation=\"LaTeX\" version=\"MathJax\">\\(\\textsf{NP}\\)<\/jats:tex-math>\n                    <\/jats:inline-formula>\n                    -hard, the above global cut version is known to admit a quasi-polynomial randomized\n                    <jats:inline-formula content-type=\"math\/tex\">\n                      <jats:tex-math notation=\"LaTeX\" version=\"MathJax\">\\(n^{\\mathcal{O}(\\log\\mathrm{OPT})}\\)<\/jats:tex-math>\n                    <\/jats:inline-formula>\n                    -time algorithm. They consider this as \u201cstrong evidence that this problem is in\n                    <jats:inline-formula content-type=\"math\/tex\">\n                      <jats:tex-math notation=\"LaTeX\" version=\"MathJax\">\\(\\textsf{P}\\)<\/jats:tex-math>\n                    <\/jats:inline-formula>\n                    .\u201d We show that this is actually not the case. We complete the study of the complexity of the\n                    <jats:sc>Global Label Min-Cut<\/jats:sc>\n                    problem by showing that the quasi-polynomial running time is probably optimal: We show that the existence of an algorithm with running time\n                    <jats:inline-formula content-type=\"math\/tex\">\n                      <jats:tex-math notation=\"LaTeX\" version=\"MathJax\">\\((np)^{o(\\log n\/(\\log\\log n)^{2})}\\)<\/jats:tex-math>\n                    <\/jats:inline-formula>\n                    would contradict the Exponential Time Hypothesis, where\n                    <jats:inline-formula content-type=\"math\/tex\">\n                      <jats:tex-math notation=\"LaTeX\" version=\"MathJax\">\\( n \\)<\/jats:tex-math>\n                    <\/jats:inline-formula>\n                    is the number of vertices, and\n                    <jats:inline-formula content-type=\"math\/tex\">\n                      <jats:tex-math notation=\"LaTeX\" version=\"MathJax\">\\( p \\)<\/jats:tex-math>\n                    <\/jats:inline-formula>\n                    is the number of labels in the input. The key step for the lower bound is a proof that\n                    <jats:sc>Global Label Min-Cut<\/jats:sc>\n                    is\n                    <jats:inline-formula content-type=\"math\/tex\">\n                      <jats:tex-math notation=\"LaTeX\" version=\"MathJax\">\\(\\textsf{W}\\)<\/jats:tex-math>\n                    <\/jats:inline-formula>\n                    [1]-hard when parameterized by the\n                    <jats:italic toggle=\"yes\">number of uncut labels<\/jats:italic>\n                    . In other words, the problem is difficult in the regime where almost all labels need to be cut to disconnect the graph.\n                  <\/jats:p>","DOI":"10.1145\/3796220","type":"journal-article","created":{"date-parts":[[2026,2,11]],"date-time":"2026-02-11T17:27:42Z","timestamp":1770830862000},"page":"1-12","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":0,"title":["A Tight Quasi-Polynomial Bound for Global Label Min-Cut"],"prefix":"10.1145","volume":"22","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-4856-5863","authenticated-orcid":false,"given":"Lars","family":"Jaffke","sequence":"first","affiliation":[{"name":"NHH Norwegian School of Economics, Bergen, Norway"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-9304-4536","authenticated-orcid":false,"given":"Paloma","family":"T. de Lima","sequence":"additional","affiliation":[{"name":"NHH Norwegian School of Economics, Bergen, Norway and IT University of Copenhagen, Copenhagen, Denmark"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-8524-4036","authenticated-orcid":false,"given":"Tom\u00e1\u0161","family":"Masa\u0159\u00edk","sequence":"additional","affiliation":[{"name":"University of Warsaw, Warsaw, Poland"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-5680-7397","authenticated-orcid":false,"given":"Marcin","family":"Pilipczuk","sequence":"additional","affiliation":[{"name":"University of Warsaw, Warsaw, Poland"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-5320-9209","authenticated-orcid":false,"given":"Uev\u00e9rton S.","family":"Souza","sequence":"additional","affiliation":[{"name":"Fluminense Federal University, Niteroi, Brazil, IMPA, Rio de Janeiro, Brazil, and University of Warsaw, Warsaw, Poland"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2026,4,7]]},"reference":[{"key":"e_1_3_2_2_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2014.02.025"},{"key":"e_1_3_2_3_2","doi-asserted-by":"publisher","DOI":"10.1111\/itor.12494"},{"key":"e_1_3_2_4_2","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS57990.2023.00037"},{"key":"e_1_3_2_5_2","doi-asserted-by":"publisher","DOI":"10.1007\/s10107-019-01443-7"},{"key":"e_1_3_2_6_2","first-page":"17","article-title":"M\u00e9moire sur les nombres premiers","volume":"7","author":"Chebyshev Pafnuty","year":"1854","unstructured":"Pafnuty Chebyshev. 1854. M\u00e9moire sur les nombres premiers. M\u00e9moires de l\u2019Acad\u00e9mie Imp\u00e9riale des Sciences de Saint-P\u00e9tersbourg 7 (1854), 17\u201333.","journal-title":"M\u00e9moires de l\u2019Acad\u00e9mie Imp\u00e9riale des Sciences de Saint-P\u00e9tersbourg"},{"key":"e_1_3_2_7_2","doi-asserted-by":"publisher","DOI":"10.1145\/3728631"},{"key":"e_1_3_2_8_2","doi-asserted-by":"publisher","DOI":"10.1142\/S0129626407002958"},{"key":"e_1_3_2_9_2","doi-asserted-by":"publisher","DOI":"10.46298\/dmtcs.1297"},{"key":"e_1_3_2_10_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2010.02.012"},{"key":"e_1_3_2_11_2","doi-asserted-by":"publisher","DOI":"10.4153\/CJM-1956-045-5"},{"key":"e_1_3_2_12_2","doi-asserted-by":"publisher","DOI":"10.1515\/9781400875184"},{"key":"e_1_3_2_13_2","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611975482.54"},{"key":"e_1_3_2_14_2","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS52979.2021.00058"},{"key":"e_1_3_2_15_2","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.ICALP.2020.57"},{"key":"e_1_3_2_16_2","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611974782.71"},{"key":"e_1_3_2_17_2","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.2001.1774"},{"key":"e_1_3_2_18_2","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611977554.CH12"},{"key":"e_1_3_2_19_2","first-page":"21","volume-title":"Proceedings of the 4th Annual ACM-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-SIAM Symposium on Discrete Algorithms (SODA \u201993). Vijaya Ramachandran (Ed.), ACM\/SIAM, 21\u201330. Retrieved from http:\/\/dl.acm.org\/citation.cfm?id=313559.313605"},{"key":"e_1_3_2_20_2","doi-asserted-by":"publisher","DOI":"10.1145\/331605.331608"},{"key":"e_1_3_2_21_2","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611977936.35"},{"key":"e_1_3_2_22_2","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS46700.2020.00020"},{"key":"e_1_3_2_23_2","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2016.70"},{"key":"e_1_3_2_24_2","doi-asserted-by":"publisher","DOI":"10.4086\/toc.2010.v006a005"},{"key":"e_1_3_2_25_2","doi-asserted-by":"publisher","DOI":"10.5555\/313559.313872"},{"key":"e_1_3_2_26_2","doi-asserted-by":"publisher","DOI":"10.1137\/0405004"},{"key":"e_1_3_2_27_2","doi-asserted-by":"publisher","DOI":"10.5555\/313651.313669"},{"key":"e_1_3_2_28_2","doi-asserted-by":"publisher","DOI":"10.1007\/BF01585863"},{"key":"e_1_3_2_29_2","doi-asserted-by":"publisher","DOI":"10.1007\/s004930070017"},{"key":"e_1_3_2_30_2","doi-asserted-by":"publisher","DOI":"10.1145\/263867.263872"},{"key":"e_1_3_2_31_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-29344-3_55"},{"key":"e_1_3_2_32_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-06089-7_18"},{"key":"e_1_3_2_33_2","doi-asserted-by":"publisher","DOI":"10.1007\/s10878-009-9222-0"},{"key":"e_1_3_2_34_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2016.08.006"},{"key":"e_1_3_2_35_2","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-016-0265-1"},{"key":"e_1_3_2_36_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.ic.2020.104543"}],"container-title":["ACM Transactions on Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3796220","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,4,7]],"date-time":"2026-04-07T14:16:13Z","timestamp":1775571373000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3796220"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2026,4,7]]},"references-count":35,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2026,4,30]]}},"alternative-id":["10.1145\/3796220"],"URL":"https:\/\/doi.org\/10.1145\/3796220","relation":{},"ISSN":["1549-6325","1549-6333"],"issn-type":[{"value":"1549-6325","type":"print"},{"value":"1549-6333","type":"electronic"}],"subject":[],"published":{"date-parts":[[2026,4,7]]},"assertion":[{"value":"2024-02-02","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2026-01-24","order":2,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2026-04-07","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}