{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,7]],"date-time":"2026-02-07T04:31:28Z","timestamp":1770438688349,"version":"3.49.0"},"reference-count":66,"publisher":"Association for Computing Machinery (ACM)","issue":"2","content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Algorithms"],"published-print":{"date-parts":[[2026,4,30]]},"abstract":"\n We consider the\n Edge Multiway Cut<\/jats:sc>\n problem on planar graphs. It is known that this can be solved in\n \n \\(n^{{O}(\\sqrt{t})}\\)<\/jats:tex-math>\n <\/jats:inline-formula>\n time (Klein and Marx) and not in\n \n \\(n^{o(\\sqrt{t})}\\)<\/jats:tex-math>\n <\/jats:inline-formula>\n time under the Exponential Time Hypothesis (Marx), where\n \n \\( t \\)<\/jats:tex-math>\n <\/jats:inline-formula>\n is the number of terminals. A stronger parameter is the number\n \n \\( k \\)<\/jats:tex-math>\n <\/jats:inline-formula>\n of faces of the planar graph that jointly cover all terminals. For the related\n Steiner Tree<\/jats:sc>\n problem, an\n \n \\(n^{{O}(\\sqrt{k})}\\)<\/jats:tex-math>\n <\/jats:inline-formula>\n time algorithm was recently shown (Kisfaludi-Bak et al.). By a completely different approach, we prove in this article that\n Edge Multiway Cut<\/jats:sc>\n can be solved in\n \n \\(n^{{O}(\\sqrt{k})}\\)<\/jats:tex-math>\n <\/jats:inline-formula>\n time as well. Our approach employs several major concepts on planar graphs, including homotopy and sphere-cut decomposition. We also mix a global treewidth dynamic program with a Dreyfus-Wagner style dynamic program to locally deal with large numbers of terminals.\n <\/jats:p>","DOI":"10.1145\/3776738","type":"journal-article","created":{"date-parts":[[2025,11,17]],"date-time":"2025-11-17T14:13:59Z","timestamp":1763388839000},"page":"1-60","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":0,"title":["Planar Multiway Cut with Terminals on Few Faces"],"prefix":"10.1145","volume":"22","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-5728-1120","authenticated-orcid":false,"given":"Sukanya","family":"Pandey","sequence":"first","affiliation":[{"name":"Department of Computer Science, RWTH Aachen University, Aachen, Germany"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-5240-7257","authenticated-orcid":false,"given":"Erik Jan","family":"van Leeuwen","sequence":"additional","affiliation":[{"name":"Department of Information and Computing Sciences, Utrecht University, Utrecht, Netherlands"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2026,2,6]]},"reference":[{"key":"e_1_3_2_2_2","doi-asserted-by":"publisher","DOI":"10.1145\/290179.290180"},{"key":"e_1_3_2_3_2","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611977073.82"},{"key":"e_1_3_2_4_2","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611973099.54"},{"key":"e_1_3_2_5_2","doi-asserted-by":"publisher","DOI":"10.1145\/2027216.2027219"},{"key":"e_1_3_2_6_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-33293-7_12"},{"key":"e_1_3_2_7_2","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-018-0443-4"},{"key":"e_1_3_2_8_2","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-022-00936-w"},{"key":"e_1_3_2_9_2","doi-asserted-by":"publisher","DOI":"10.1002\/net.3230200110"},{"key":"e_1_3_2_10_2","doi-asserted-by":"publisher","DOI":"10.1137\/0217004"},{"key":"e_1_3_2_11_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-73951-7_25"},{"key":"e_1_3_2_12_2","doi-asserted-by":"publisher","DOI":"10.1137\/0406027"},{"key":"e_1_3_2_13_2","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.1999.1687"},{"key":"e_1_3_2_14_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.ipl.2013.12.001"},{"key":"e_1_3_2_15_2","doi-asserted-by":"publisher","DOI":"10.1145\/1137856.1137918"},{"key":"e_1_3_2_16_2","doi-asserted-by":"publisher","DOI":"10.1145\/1542362.1542426"},{"key":"e_1_3_2_17_2","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-003-1061-2"},{"key":"e_1_3_2_18_2","doi-asserted-by":"publisher","DOI":"10.1145\/335305.335359"},{"key":"e_1_3_2_19_2","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-007-9130-6"},{"key":"e_1_3_2_20_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.orl.2010.03.003"},{"key":"e_1_3_2_21_2","doi-asserted-by":"publisher","DOI":"10.1137\/12086217X"},{"key":"e_1_3_2_22_2","doi-asserted-by":"publisher","DOI":"10.1137\/18M1183297"},{"key":"e_1_3_2_23_2","doi-asserted-by":"publisher","DOI":"10.1145\/3450704"},{"key":"e_1_3_2_24_2","doi-asserted-by":"publisher","DOI":"10.1145\/2462896.2462899"},{"key":"e_1_3_2_25_2","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539792225297"},{"key":"e_1_3_2_26_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-48350-3_32"},{"key":"e_1_3_2_27_2","volume-title":"Graph Theory","author":"Diestel Reinhard","year":"2005","unstructured":"Reinhard Diestel. 2005. Graph Theory (3rd ed.). Springer.","edition":"3"},{"key":"e_1_3_2_28_2","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-009-9296-1"},{"key":"e_1_3_2_29_2","doi-asserted-by":"publisher","DOI":"10.1002\/net.3230010302"},{"key":"e_1_3_2_30_2","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611973099.103"},{"key":"e_1_3_2_31_2","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611973082.88"},{"key":"e_1_3_2_32_2","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611973082.25"},{"key":"e_1_3_2_33_2","doi-asserted-by":"publisher","DOI":"10.5555\/2783147.2783151"},{"key":"e_1_3_2_34_2","doi-asserted-by":"publisher","DOI":"10.4153\/CJM-1956-045-5"},{"key":"e_1_3_2_35_2","first-page":"139","volume-title":"Proceedings of the DIMACS Workshop on Polyhedral Combinatorics 1989, DIMACS Series in Discrete Mathematics and Theoretical Computer Science","author":"Frank Andr\u00e1s","year":"1990","unstructured":"Andr\u00e1s Frank and Alexander Schrijver. 1990. Vertex-disjoint simple paths of given homotopy in a planar graph. In Proceedings of the DIMACS Workshop on Polyhedral Combinatorics 1989, DIMACS Series in Discrete Mathematics and Theoretical Computer Science, Vol. 1, DIMACS\/AMS, 139\u2013162."},{"key":"e_1_3_2_36_2","doi-asserted-by":"publisher","DOI":"10.1145\/102782.102788"},{"key":"e_1_3_2_37_2","first-page":"14:1","volume-title":"Proceedings of the International Conference on Parameterized and Exact Computation 2022","author":"Galby Esther","year":"2022","unstructured":"Esther Galby, D\u00e1niel Marx, Philipp Schepper, Roohani Sharma, and Prafullkumar Tale. 2022. Domination and cut problems on chordal graphs with bounded leafage. In Proceedings of the International Conference on Parameterized and Exact Computation 2022, LIPIcs, Vol. 249, Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik, 14:1\u201314:24."},{"key":"e_1_3_2_38_2","doi-asserted-by":"publisher","DOI":"10.1090\/S0894-0347-08-00624-3"},{"key":"e_1_3_2_39_2","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-012-9627-5"},{"key":"e_1_3_2_40_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.disopt.2010.05.003"},{"key":"e_1_3_2_41_2","doi-asserted-by":"publisher","DOI":"10.1016\/S0166-218X(98)00036-5"},{"key":"e_1_3_2_42_2","doi-asserted-by":"publisher","DOI":"10.1145\/321850.321852"},{"key":"e_1_3_2_43_2","unstructured":"Te C. Hu. 1969. Integer Programming and Network Flows. Technical Report. Wisconsin University Madison Department of Computer Sciences."},{"key":"e_1_3_2_44_2","doi-asserted-by":"publisher","DOI":"10.1137\/20M1353782"},{"key":"e_1_3_2_45_2","doi-asserted-by":"publisher","DOI":"10.1145\/301250.301430"},{"key":"e_1_3_2_46_2","doi-asserted-by":"publisher","DOI":"10.1145\/3371389"},{"key":"e_1_3_2_47_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-31594-7_48"},{"key":"e_1_3_2_48_2","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2012.46"},{"key":"e_1_3_2_49_2","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611975482.33"},{"key":"e_1_3_2_50_2","doi-asserted-by":"publisher","DOI":"10.1137\/17M1151225"},{"key":"e_1_3_2_51_2","doi-asserted-by":"publisher","DOI":"10.1137\/0136016"},{"key":"e_1_3_2_52_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2005.10.007"},{"key":"e_1_3_2_53_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-31594-7_57"},{"key":"e_1_3_2_54_2","first-page":"28","volume-title":"Proceedings of the International Colloquium Conference on Automata, Languages, and Programming 2013","author":"Marx D\u00e1niel","year":"2013","unstructured":"D\u00e1niel Marx. 2013. The square root phenomenon in planar graphs. In Proceedings of the International Colloquium Conference on Automata, Languages, and Programming 2013, LNCS, Vol. 7966. Springer, 28."},{"key":"e_1_3_2_55_2","unstructured":"D\u00e1niel Marx. 2015. The Square Root Phenomenon in Planar Graphs: Survey and New Results. Presentation at Simons Institute Berkeley in Workshop Satisfiability Lower Bounds and Tight Results for Parameterized and Exponential-Time Algorithms. Retrieved from https:\/\/simons.berkeley.edu\/talks\/square-root-phenomenon-planar-graphs-survey-new-results"},{"key":"e_1_3_2_56_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-48350-3_72"},{"key":"e_1_3_2_57_2","doi-asserted-by":"publisher","DOI":"10.1137\/0214023"},{"key":"e_1_3_2_58_2","first-page":"70:1","volume-title":"Proceedings of the International Symposium on Mathematical Foundational of Computer Science 2020","author":"Misra Pranabendu","year":"2020","unstructured":"Pranabendu Misra, Fahad Panolan, Ashutosh Rai, Saket Saurabh, and Roohani Sharma. 2020. Quick separation in chordal and split graphs. In Proceedings of the International Symposium on Mathematical Foundational of Computer Science 2020, LIPIcs, Vol. 170. Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik, 70:1\u201370:14."},{"key":"e_1_3_2_59_2","doi-asserted-by":"publisher","DOI":"10.1145\/167088.167284"},{"key":"e_1_3_2_60_2","doi-asserted-by":"publisher","DOI":"10.1145\/3239560"},{"key":"e_1_3_2_61_2","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-019-00670-w"},{"key":"e_1_3_2_62_2","doi-asserted-by":"publisher","DOI":"10.1137\/0212005"},{"key":"e_1_3_2_63_2","doi-asserted-by":"publisher","DOI":"10.1007\/BF01215352"},{"key":"e_1_3_2_64_2","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(74)90003-9"},{"key":"e_1_3_2_65_2","doi-asserted-by":"publisher","DOI":"10.1145\/3501304"},{"key":"e_1_3_2_66_2","doi-asserted-by":"publisher","DOI":"10.1007\/s00224-009-9215-5"},{"key":"e_1_3_2_67_2","doi-asserted-by":"publisher","DOI":"10.1006\/jagm.2000.1148"}],"container-title":["ACM Transactions on Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3776738","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,2,6]],"date-time":"2026-02-06T14:22:39Z","timestamp":1770387759000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3776738"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2026,2,6]]},"references-count":66,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2026,4,30]]}},"alternative-id":["10.1145\/3776738"],"URL":"https:\/\/doi.org\/10.1145\/3776738","relation":{},"ISSN":["1549-6325","1549-6333"],"issn-type":[{"value":"1549-6325","type":"print"},{"value":"1549-6333","type":"electronic"}],"subject":[],"published":{"date-parts":[[2026,2,6]]},"assertion":[{"value":"2024-08-02","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2025-11-04","order":2,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2026-02-06","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}