{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,7]],"date-time":"2026-02-07T19:27:51Z","timestamp":1770492471142,"version":"3.49.0"},"reference-count":37,"publisher":"Association for Computing Machinery (ACM)","issue":"4","license":[{"start":{"date-parts":[[2021,7,14]],"date-time":"2021-07-14T00:00:00Z","timestamp":1626220800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"French ANR project","award":["ANR-18-CE40-0004-01 (FOCAL), ANR-17-CE40-0033 (SoS), ANR-19-CE40-0014 (MIN-MAX), ANR-16-CE40-0009-01 (GATO)"],"award-info":[{"award-number":["ANR-18-CE40-0004-01 (FOCAL), ANR-17-CE40-0033 (SoS), ANR-19-CE40-0014 (MIN-MAX), ANR-16-CE40-0009-01 (GATO)"]}]},{"name":"ERC Consolidator Grant SYSTEMATICGRAPH","award":["725978"],"award-info":[{"award-number":["725978"]}]},{"name":"CNRS PEPS project COMP3D"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["J. ACM"],"published-print":{"date-parts":[[2021,8]]},"abstract":"<jats:p>\n            We prove essentially tight lower bounds, conditionally to the Exponential Time Hypothesis, for two fundamental but seemingly very different cutting problems on surface-embedded graphs: the\n            <jats:sc>Shortest Cut Graph<\/jats:sc>\n            problem and the\n            <jats:sc>Multiway Cut<\/jats:sc>\n            problem.\n          <\/jats:p>\n          <jats:p>\n            A cut graph of a graph\u00a0\n            <jats:italic>G<\/jats:italic>\n            embedded on a surface\u00a0S is a subgraph of\u00a0\n            <jats:italic>G<\/jats:italic>\n            whose removal from\u00a0S leaves a disk. We consider the problem of deciding whether an unweighted graph embedded on a surface of genus\u00a0\n            <jats:italic>G<\/jats:italic>\n            has a cut graph of length at most a given value. We prove a time lower bound for this problem of\n            <jats:italic>n<\/jats:italic>\n            <jats:sup>\n              \u03a9(\n              <jats:italic>g<\/jats:italic>\n              log\n              <jats:italic>g<\/jats:italic>\n              )\n            <\/jats:sup>\n            conditionally to the ETH. In other words, the first\n            <jats:italic>n<\/jats:italic>\n            <jats:sup>\n              <jats:italic>O(g)<\/jats:italic>\n            <\/jats:sup>\n            -time algorithm by Erickson and Har-Peled [SoCG 2002, Discr. Comput. Geom. 2004] is essentially optimal. We also prove that the problem is W[1]-hard when parameterized by the genus, answering a 17-year-old question of these authors.\n          <\/jats:p>\n          <jats:p>\n            A multiway cut of an undirected graph\u00a0\n            <jats:italic>G<\/jats:italic>\n            with\n            <jats:italic>t<\/jats:italic>\n            distinguished vertices, called\n            <jats:italic>terminals<\/jats:italic>\n            , is a set of edges whose removal disconnects all pairs of terminals. We consider the problem of deciding whether an unweighted graph\u00a0\n            <jats:italic>G<\/jats:italic>\n            has a multiway cut of weight at most a given value. We prove a time lower bound for this problem of\n            <jats:italic>n<\/jats:italic>\n            <jats:sup>\n              \u03a9(\n              <jats:italic>gt<\/jats:italic>\n              +\n              <jats:italic>g<\/jats:italic>\n              <jats:sup>2<\/jats:sup>\n              +\n              <jats:italic>t<\/jats:italic>\n              log (\n              <jats:italic>g<\/jats:italic>\n              +\n              <jats:italic>t<\/jats:italic>\n              ))\n            <\/jats:sup>\n            , conditionally to the ETH, for any choice of the genus\u00a0\n            <jats:italic>g<\/jats:italic>\n            \u2265 0 of the graph and the number of terminals\u00a0\n            <jats:italic>t<\/jats:italic>\n            \u2265 4. In other words, the algorithm by the second author [Algorithmica 2017] (for the more general multicut problem) is essentially optimal; this extends the lower bound by the third author [ICALP 2012] (for the planar case).\n          <\/jats:p>\n          <jats:p>\n            Reductions to planar problems usually involve a gridlike structure. The main novel idea for our results is to understand what structures instead of grids are needed if we want to exploit optimally a certain value\u00a0\n            <jats:italic>G<\/jats:italic>\n            of the genus.\n          <\/jats:p>","DOI":"10.1145\/3450704","type":"journal-article","created":{"date-parts":[[2021,7,14]],"date-time":"2021-07-14T16:23:56Z","timestamp":1626279836000},"page":"1-26","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":3,"title":["Almost Tight Lower Bounds for Hard Cutting Problems in Embedded Graphs"],"prefix":"10.1145","volume":"68","author":[{"given":"Vincent","family":"Cohen-Addad","sequence":"first","affiliation":[{"name":"Sorbonne Universit\u00e9s, UPMC Univ Paris 06, CNRS, LIP6, Paris, France"}]},{"given":"\u00c9ric Colin","family":"de Verdi\u00e8re","sequence":"additional","affiliation":[{"name":"LIGM, CNRS, Univ Gustave Eiffel, Marne-la-Vall\u00e9e, France"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-5686-8314","authenticated-orcid":false,"given":"D\u00e1niel","family":"Marx","sequence":"additional","affiliation":[{"name":"CISPA Helmholtz Center for Information Security, Germany"}]},{"given":"Arnaud","family":"de Mesmay","sequence":"additional","affiliation":[{"name":"LIGM, CNRS, Univ Gustave Eiffel, Marne-la-Vall\u00e9e, France"}]}],"member":"320","published-online":{"date-parts":[[2021,7,14]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2006.11.001"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.5555\/2634074.2634203"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.5555\/3174304.3175400"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-48350-3_33"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-016-0258-0"},{"key":"e_1_2_1_6_1","volume-title":"Handbook of Discrete and Computational Geometry","author":"de Verdi\u00e8re \u00c9ric Colin","unstructured":"\u00c9ric Colin de Verdi\u00e8re . 2018. Computational topology of graphs on surfaces . In Handbook of Discrete and Computational Geometry ( 3 rd ed.), Jacob E. Goodman, Joseph O\u2019Rourke, and Csaba Toth (Eds.). CRC Press LLC , 605\u2013636. \u00c9ric Colin de Verdi\u00e8re. 2018. Computational topology of graphs on surfaces. In Handbook of Discrete and Computational Geometry (3rd ed.), Jacob E. Goodman, Joseph O\u2019Rourke, and Csaba Toth (Eds.). CRC Press LLC, 605\u2013636.","edition":"3"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.5555\/2884435.2884548"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.5555\/2815661"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539792225297"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/3188745.3188854"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/1101821.1101823"},{"key":"e_1_2_1_12_1","volume-title":"Graph Theory","author":"Diestel Reinhard","unstructured":"Reinhard Diestel . 2000. Graph Theory . Springer-Verlag . Retrieved from http:\/\/diestel-graph-theory.com\/. Reinhard Diestel. 2000. Graph Theory. Springer-Verlag. Retrieved from http:\/\/diestel-graph-theory.com\/."},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00454-003-2948-z"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2016.62"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.5555\/2621979"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/1206035.1206036"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jctb.2008.06.004"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/380752.380867"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1090\/S0273-0979-06-01126-8"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.5555\/795664.796440"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.2001.1774"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2008.53"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-31594-7_48"},{"key":"e_1_2_1_25_1","volume-title":"et\u00a0al","author":"Lokshtanov Daniel","year":"2013","unstructured":"Daniel Lokshtanov , D\u00e1niel Marx , Saket Saurabh , et\u00a0al . 2013 . Lower bounds based on the exponential time hypothesis. Bull. EATCS 3, 105 (2013). Daniel Lokshtanov, D\u00e1niel Marx, Saket Saurabh, et\u00a0al. 2013. Lower bounds based on the exponential time hypothesis. Bull. EATCS 3, 105 (2013)."},{"key":"e_1_2_1_26_1","volume-title":"Proceedings of the IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS\u201912)","author":"Lokshtanov Daniel","year":"2012","unstructured":"Daniel Lokshtanov , Saket Saurabh , and Magnus Wahlstr\u00f6m . 2012 . Subexponential parameterized odd cycle transversal on planar graphs . In Proceedings of the IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS\u201912) . 424\u2013434. Daniel Lokshtanov, Saket Saurabh, and Magnus Wahlstr\u00f6m. 2012. Subexponential parameterized odd cycle transversal on planar graphs. In Proceedings of the IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS\u201912). 424\u2013434."},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.4007\/annals.2015.182.1.7"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2007.50"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.4086\/toc.2010.v006a005"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-31594-7_57"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-39212-2_4"},{"key":"e_1_2_1_32_1","volume-title":"Proceedings of the 31st International Symposium on Theoretical Aspects of Computer Science (STACS\u201914)","volume":"25","author":"Marx D\u00e1niel","year":"2014","unstructured":"D\u00e1niel Marx and Micha\u0142 Pilipczuk . 2014 . Everything you always wanted to know about the parameterized complexity of Subgraph Isomorphism (but were afraid to ask) . In Proceedings of the 31st International Symposium on Theoretical Aspects of Computer Science (STACS\u201914) , Vol. 25 . 542\u2013553. D\u00e1niel Marx and Micha\u0142 Pilipczuk. 2014. Everything you always wanted to know about the parameterized complexity of Subgraph Isomorphism (but were afraid to ask). In Proceedings of the 31st International Symposium on Theoretical Aspects of Computer Science (STACS\u201914), Vol. 25. 542\u2013553."},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-48350-3_72"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2018.00052"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1145\/2582112.2582124"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1137\/S089548019529248X"},{"key":"e_1_2_1_37_1","volume-title":"Graphs on Surfaces","author":"Mohar Bojan","unstructured":"Bojan Mohar and Carsten Thomassen . 2001. Graphs on Surfaces . Johns Hopkins University Press . Bojan Mohar and Carsten Thomassen. 2001. Graphs on Surfaces. Johns Hopkins University Press."},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1145\/990002.990007"}],"container-title":["Journal of the ACM"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3450704","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3450704","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T21:28:41Z","timestamp":1750195721000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3450704"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,7,14]]},"references-count":37,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2021,8]]}},"alternative-id":["10.1145\/3450704"],"URL":"https:\/\/doi.org\/10.1145\/3450704","relation":{},"ISSN":["0004-5411","1557-735X"],"issn-type":[{"value":"0004-5411","type":"print"},{"value":"1557-735X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2021,7,14]]},"assertion":[{"value":"2019-10-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2021-02-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2021-07-14","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}