{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,2]],"date-time":"2026-03-02T15:40:27Z","timestamp":1772466027118,"version":"3.50.1"},"reference-count":61,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2025,10,22]],"date-time":"2025-10-22T00:00:00Z","timestamp":1761091200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2025,10,22]],"date-time":"2025-10-22T00:00:00Z","timestamp":1761091200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"name":"CISPA - Helmholtz-Zentrum f\u00fcr Informationssicherheit gGmbH"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Discrete Comput Geom"],"published-print":{"date-parts":[[2026,3]]},"abstract":"Abstract<\/jats:title>\n \n The\n Multicut<\/jats:sc>\n problem asks for a minimum cut separating certain pairs of vertices: formally, given a graph\n G<\/jats:italic>\n and a demand graph\n H<\/jats:italic>\n on a set\n \n \n $$T\\subseteq V(G)$$<\/jats:tex-math>\n \n \n T<\/mml:mi>\n \u2286<\/mml:mo>\n V<\/mml:mi>\n (<\/mml:mo>\n G<\/mml:mi>\n )<\/mml:mo>\n <\/mml:mrow>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula>\n of terminals, the task is to find a minimum-weight set\n C<\/jats:italic>\n of edges of\n G<\/jats:italic>\n such that whenever two vertices of\n T<\/jats:italic>\n are adjacent in\n H<\/jats:italic>\n , they are in different components of\n \n \n $$G\\setminus C$$<\/jats:tex-math>\n \n \n G<\/mml:mi>\n \\<\/mml:mo>\n C<\/mml:mi>\n <\/mml:mrow>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula>\n . Colin de Verdi\u00e8re [\n Algorithmica,<\/jats:italic>\n 2017] showed that\n Multicut<\/jats:sc>\n with\n t<\/jats:italic>\n terminals on a graph\n G<\/jats:italic>\n of genus\n g<\/jats:italic>\n can be solved in time\n \n \n $$f(t,g)n^{O(\\sqrt{g^2+gt+t})}$$<\/jats:tex-math>\n \n \n f<\/mml:mi>\n \n (<\/mml:mo>\n t<\/mml:mi>\n ,<\/mml:mo>\n g<\/mml:mi>\n )<\/mml:mo>\n <\/mml:mrow>\n \n n<\/mml:mi>\n \n O<\/mml:mi>\n (<\/mml:mo>\n \n \n \n g<\/mml:mi>\n 2<\/mml:mn>\n <\/mml:msup>\n +<\/mml:mo>\n g<\/mml:mi>\n t<\/mml:mi>\n +<\/mml:mo>\n t<\/mml:mi>\n <\/mml:mrow>\n <\/mml:msqrt>\n )<\/mml:mo>\n <\/mml:mrow>\n <\/mml:msup>\n <\/mml:mrow>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula>\n . Cohen-Addad et al.\u00a0[\n JACM<\/jats:italic>\n , 2021] proved a matching lower bound showing that the exponent of\n n<\/jats:italic>\n is essentially best possible (for every fixed value of\n t<\/jats:italic>\n and\n g<\/jats:italic>\n ), even in the special case of\n Multiway Cut<\/jats:sc>\n , where the demand graph\n H<\/jats:italic>\n is a complete graph. However, this lower bound tells us nothing about other special cases of\n Multicut<\/jats:sc>\n such as\n Group 3-Terminal Cut<\/jats:sc>\n (where three groups of terminals need to be separated from each other). We show that if the demand pattern is, in some sense, close to being a complete bipartite graph, then\n Multicut<\/jats:sc>\n can be solved faster than\n \n \n $$f(t,g)n^{O(\\sqrt{g^2+gt+t})}$$<\/jats:tex-math>\n \n \n f<\/mml:mi>\n \n (<\/mml:mo>\n t<\/mml:mi>\n ,<\/mml:mo>\n g<\/mml:mi>\n )<\/mml:mo>\n <\/mml:mrow>\n \n n<\/mml:mi>\n \n O<\/mml:mi>\n (<\/mml:mo>\n \n \n \n g<\/mml:mi>\n 2<\/mml:mn>\n <\/mml:msup>\n +<\/mml:mo>\n g<\/mml:mi>\n t<\/mml:mi>\n +<\/mml:mo>\n t<\/mml:mi>\n <\/mml:mrow>\n <\/mml:msqrt>\n )<\/mml:mo>\n <\/mml:mrow>\n <\/mml:msup>\n <\/mml:mrow>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula>\n , and furthermore this is the only property that allows such an improvement. Formally, for a class\n \n \n $$\\mathcal {H}$$<\/jats:tex-math>\n \n H<\/mml:mi>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula>\n of graphs,\n \n \n $$\\textsc {Multicut}(\\mathcal {H})$$<\/jats:tex-math>\n \n \n M<\/mml:mi>\n \n U<\/mml:mi>\n L<\/mml:mi>\n T<\/mml:mi>\n I<\/mml:mi>\n C<\/mml:mi>\n U<\/mml:mi>\n T<\/mml:mi>\n <\/mml:mstyle>\n (<\/mml:mo>\n H<\/mml:mi>\n )<\/mml:mo>\n <\/mml:mrow>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula>\n is the special case where the demand graph\n H<\/jats:italic>\n is in\n \n \n $$\\mathcal {H}$$<\/jats:tex-math>\n \n H<\/mml:mi>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula>\n . For every fixed class\n \n \n $$\\mathcal {H}$$<\/jats:tex-math>\n \n H<\/mml:mi>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula>\n (satisfying some mild closure property), fixed\n g<\/jats:italic>\n , and fixed\n t<\/jats:italic>\n , our main result gives tight upper and lower bounds on the exponent of\n n<\/jats:italic>\n in algorithms solving\n \n \n $$\\textsc {Multicut}(\\mathcal {H})$$<\/jats:tex-math>\n \n \n M<\/mml:mi>\n \n U<\/mml:mi>\n L<\/mml:mi>\n T<\/mml:mi>\n I<\/mml:mi>\n C<\/mml:mi>\n U<\/mml:mi>\n T<\/mml:mi>\n <\/mml:mstyle>\n (<\/mml:mo>\n H<\/mml:mi>\n )<\/mml:mo>\n <\/mml:mrow>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula>\n .\n <\/jats:p>","DOI":"10.1007\/s00454-025-00782-x","type":"journal-article","created":{"date-parts":[[2025,10,22]],"date-time":"2025-10-22T17:15:21Z","timestamp":1761153321000},"page":"537-596","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Multicut Problems in Embedded Graphs: The Dependency of Complexity on the Demand Pattern"],"prefix":"10.1007","volume":"75","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-6895-755X","authenticated-orcid":false,"given":"Jacob","family":"Focke","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-5410-613X","authenticated-orcid":false,"given":"Florian","family":"H\u00f6rsch","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Shaohua","family":"Li","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-5686-8314","authenticated-orcid":false,"given":"D\u00e1niel","family":"Marx","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2025,10,22]]},"reference":[{"issue":"2","key":"782_CR1","doi-asserted-by":"publisher","first-page":"753","DOI":"10.1007\/s00453-020-00773-9","volume":"83","author":"A Agrawal","year":"2021","unstructured":"Agrawal, A., Panolan, F., Saurabh, S., Zehavi, M.: Simultaneous feedback edge set: a parameterized perspective. Algorithmica 83(2), 753\u2013774 (2021). https:\/\/doi.org\/10.1007\/s00453-020-00773-9","journal-title":"Algorithmica"},{"key":"782_CR2","doi-asserted-by":"publisher","unstructured":"Bertel\u00e8, U., Brioschi, F.: On non-serial dynamic programming. Journal of Combinatorial Theory, Series A 14(2), 137\u2013148 (1973). https:\/\/doi.org\/10.1016\/0097-3165(73)90016-2. URL: https:\/\/www.sciencedirect.com\/science\/article\/pii\/0097316573900162","DOI":"10.1016\/0097-3165(73)90016-2"},{"issue":"4","key":"782_CR3","doi-asserted-by":"publisher","first-page":"2762","DOI":"10.1007\/s10878-021-00792-4","volume":"44","author":"J Blum","year":"2022","unstructured":"Blum, J.: W[1]-hardness of the k-center problem parameterized by the skeleton dimension. J. Comb. Optim. 44(4), 2762\u20132781 (2022). https:\/\/doi.org\/10.1007\/s10878-021-00792-4","journal-title":"J. Comb. Optim."},{"issue":"8","key":"782_CR4","doi-asserted-by":"publisher","first-page":"2360","DOI":"10.1007\/s00453-020-00730-6","volume":"82","author":"\u00c9 Bonnet","year":"2020","unstructured":"Bonnet, \u00c9., Bousquet, N., Charbit, P., Thomass\u00e9, S., Watrigant, R.: Parameterized complexity of independent set in h-free graphs. Algorithmica 82(8), 2360\u20132394 (2020). https:\/\/doi.org\/10.1007\/s00453-020-00730-6","journal-title":"Algorithmica"},{"key":"782_CR5","doi-asserted-by":"publisher","unstructured":"Bonnet, \u00c9., Giannopoulos, P., Lampis, M.: On the parameterized complexity of red-blue points separation. In: Lokshtanov, D., Nishimura, N. editors, 12th International Symposium on Parameterized and Exact Computation, IPEC 2017, September 6-8, 2017, Vienna, Austria, volume\u00a089 of LIPIcs, pages 8:1\u20138:13. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, (2017). https:\/\/doi.org\/10.4230\/LIPIcs.IPEC.2017.8","DOI":"10.4230\/LIPIcs.IPEC.2017.8"},{"key":"782_CR6","doi-asserted-by":"publisher","unstructured":"Bonnet, \u00c9., Miltzow, T.: Parameterized hardness of art gallery problems. In: Sankowski, P., Zaroliagis, Christos\u00a0D. editors, 24th Annual European Symposium on Algorithms, ESA 2016, August 22-24, 2016, Aarhus, Denmark, volume\u00a057 of LIPIcs, pages 19:1\u201319:17. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, (2016). https:\/\/doi.org\/10.4230\/LIPIcs.ESA.2016.19","DOI":"10.4230\/LIPIcs.ESA.2016.19"},{"key":"782_CR7","doi-asserted-by":"publisher","first-page":"78","DOI":"10.1016\/j.dam.2016.11.016","volume":"231","author":"\u00c9 Bonnet","year":"2017","unstructured":"Bonnet, \u00c9., Sikora, F.: The graph motif problem parameterized by the structure of the input graph. Discret. Appl. Math. 231, 78\u201394 (2017). https:\/\/doi.org\/10.1016\/j.dam.2016.11.016","journal-title":"Discret. Appl. Math."},{"key":"782_CR8","doi-asserted-by":"publisher","unstructured":"Bringmann, K., Kozma, L., Moran, S., Narayanaswamy, N.S.: Hitting set for hypergraphs of low VC-dimension. In: Sankowski, P., Zaroliagis, Christos\u00a0D. editors, 24th Annual European Symposium on Algorithms, ESA 2016, August 22-24, 2016, Aarhus, Denmark, volume\u00a057 of LIPIcs, pages 23:1\u201323:18. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, (2016). https:\/\/doi.org\/10.4230\/LIPIcs.ESA.2016.23","DOI":"10.4230\/LIPIcs.ESA.2016.23"},{"issue":"1","key":"782_CR9","doi-asserted-by":"publisher","first-page":"19","DOI":"10.1137\/19m1250121","volume":"51","author":"C Carbonnel","year":"2022","unstructured":"Carbonnel, C., Romero, M., Zivn\u00fd, S.: The complexity of general-valued constraint satisfaction problems seen from the other side. SIAM J. Comput. 51(1), 19\u201369 (2022). https:\/\/doi.org\/10.1137\/19m1250121","journal-title":"SIAM J. Comput."},{"key":"782_CR10","doi-asserted-by":"publisher","unstructured":"Chambers, E.\u00a0W., Erickson, J., Nayyeri, A.: Minimum cuts and shortest homologous cycles. In: Proceedings of the Twenty-Fifth Annual Symposium on Computational Geometry, SCG \u201909, page 377\u2013385, New York, NY, USA, (2009). Association for Computing Machinery. https:\/\/doi.org\/10.1145\/1542362.1542426","DOI":"10.1145\/1542362.1542426"},{"issue":"8","key":"782_CR11","doi-asserted-by":"publisher","first-page":"1346","DOI":"10.1016\/j.jcss.2006.04.007","volume":"72","author":"J Chen","year":"2006","unstructured":"Chen, J., Huang, X., Kanj, I.A., Xia, G.: Strong computational lower bounds via parameterized complexity. J. Comput. Syst. Sci. 72(8), 1346\u20131367 (2006). https:\/\/doi.org\/10.1016\/j.jcss.2006.04.007","journal-title":"J. Comput. Syst. Sci."},{"key":"782_CR12","unstructured":"Chitnis, R.: Refined lower bounds for nearest neighbor condensation. In: Dasgupta, S., Haghtalab, N. editors, International Conference on Algorithmic Learning Theory, 29 March - 1 April 2022, Paris, France, volume 167 of Proceedings of Machine Learning Research, pages 262\u2013281. PMLR, (2022). URL: https:\/\/proceedings.mlr.press\/v167\/chitnis22a.html"},{"issue":"2","key":"782_CR13","doi-asserted-by":"publisher","first-page":"12:1","DOI":"10.1145\/3447584","volume":"17","author":"Rajesh Chitnis","year":"2021","unstructured":"Chitnis, Rajesh, Feldmann, Andreas Emil, Manurangsi, Pasin: Parameterized approximation algorithms for bidirected Steiner network problems. ACM Trans. Algorithms 17(2), 12:1-12:68 (2021). https:\/\/doi.org\/10.1145\/3447584","journal-title":"ACM Trans. Algorithms"},{"issue":"8","key":"782_CR14","doi-asserted-by":"publisher","first-page":"3200","DOI":"10.1007\/s00453-019-00580-x","volume":"81","author":"R Chitnis","year":"2019","unstructured":"Chitnis, R., Feldmann, A.E., Such\u00fd, O.: A tight lower bound for planar Steiner orientation. Algorithmica 81(8), 3200\u20133216 (2019). https:\/\/doi.org\/10.1007\/s00453-019-00580-x","journal-title":"Algorithmica"},{"issue":"2","key":"782_CR15","doi-asserted-by":"publisher","first-page":"318","DOI":"10.1137\/18M122371X","volume":"49","author":"R. H. Chitnis","year":"2020","unstructured":"Chitnis, R.. H.., Feldmann, A.. E.., Hajiaghayi, M.. T.., Marx, D..: Tight bounds for planar strongly connected Steiner subgraph with fixed number of terminals (and extensions). SIAM J. Comput. 49(2), 318\u2013364 (2020). https:\/\/doi.org\/10.1137\/18M122371X","journal-title":"SIAM J. Comput."},{"key":"782_CR16","doi-asserted-by":"publisher","unstructured":"Cohen-Addad, V., Colin, \u00c9., Verdi\u00e8re, D., Marx, de Mesmay, A.: Almost tight lower bounds for hard cutting problems in embedded graphs. J. ACM 68(4), 30:1-30:26 (2021). https:\/\/doi.org\/10.1145\/3450704","DOI":"10.1145\/3450704"},{"key":"782_CR17","doi-asserted-by":"crossref","unstructured":"de Verdi\u00e8re, \u00c9. C.: Multicuts in planar and bounded-genus graphs with bounded number of terminals. Algorithmica, 78:1206 \u2013 1224, (2017). URL: https:\/\/api.semanticscholar.org\/CorpusID:686950","DOI":"10.1007\/s00453-016-0258-0"},{"key":"782_CR18","doi-asserted-by":"publisher","unstructured":"Curticapean, R., Dell, H., Husfeldt, T.: Modular counting of subgraphs: Matchings, matching-splittable graphs, and paths. In: Mutzel, P., Pagh, R., Herman, G. editors, 29th Annual European Symposium on Algorithms, ESA 2021, September 6-8, 2021, Lisbon, Portugal (Virtual Conference), volume 204 of LIPIcs, pages 34:1\u201334:17. Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik, 2021. https:\/\/doi.org\/10.4230\/LIPIcs.ESA.2021.34","DOI":"10.4230\/LIPIcs.ESA.2021.34"},{"key":"782_CR19","doi-asserted-by":"publisher","unstructured":"Curticapean, R., Dell, H., Marx, D.: Homomorphisms are a good basis for counting small subgraphs. In: Hatami, H., McKenzie, P., King, V. editors, Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2017, Montreal, QC, Canada, June 19-23, 2017, pages 210\u2013223. ACM, (2017). https:\/\/doi.org\/10.1145\/3055399.3055502","DOI":"10.1145\/3055399.3055502"},{"key":"782_CR20","doi-asserted-by":"publisher","unstructured":"Curticapean, R., Xia, M.: Parameterizing the permanent: Genus, apices, minors, evaluation mod 2k. In: Guruswami, V. editor, IEEE 56th Annual Symposium on Foundations of Computer Science, FOCS 2015, Berkeley, CA, USA, 17-20 October, 2015, pages 994\u20131009. IEEE Computer Society, (2015). https:\/\/doi.org\/10.1109\/FOCS.2015.65","DOI":"10.1109\/FOCS.2015.65"},{"key":"782_CR21","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-21275-3","volume-title":"Parameterized Algorithms","author":"M Cygan","year":"2015","unstructured":"Cygan, M., Fomin, F.V., Kowalik, L., Lokshtanov, D., Marx, D., Pilipczuk, M., Pilipczuk, M., Saurabh, S.: Parameterized Algorithms. Springer (2015). https:\/\/doi.org\/10.1007\/978-3-319-21275-3"},{"issue":"4","key":"782_CR22","doi-asserted-by":"publisher","first-page":"864","DOI":"10.1137\/S0097539792225297","volume":"23","author":"E Dahlhaus","year":"1994","unstructured":"Dahlhaus, E., Johnson, D.S., Papadimitriou, C.H., Seymour, P.D., Yannakakis, M.: The complexity of multiterminal cuts. SIAM J. Comput. 23(4), 864\u2013894 (1994). https:\/\/doi.org\/10.1137\/S0097539792225297","journal-title":"SIAM J. Comput."},{"key":"782_CR23","doi-asserted-by":"publisher","first-page":"18","DOI":"10.1016\/j.tcs.2018.10.007","volume":"769","author":"M de Berg","year":"2019","unstructured":"de Berg, M., Kisfaludi-Bak, S., Woeginger, G.J.: The complexity of dominating set in geometric intersection graphs. Theor. Comput. Sci. 769, 18\u201331 (2019). https:\/\/doi.org\/10.1016\/j.tcs.2018.10.007","journal-title":"Theor. Comput. Sci."},{"issue":"1","key":"782_CR24","doi-asserted-by":"publisher","first-page":"33","DOI":"10.1145\/1077464.1077468","volume":"1","author":"ED Demaine","year":"2005","unstructured":"Demaine, E.D., Fomin, F.V., Hajiaghayi, M., Thilikos, D.M.: Fixed-parameter algorithms for (k, r)-center in planar graphs and map graphs. ACM Trans. Algorithms 1(1), 33\u201347 (2005). https:\/\/doi.org\/10.1145\/1077464.1077468","journal-title":"ACM Trans. Algorithms"},{"key":"782_CR25","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-53622-3","volume-title":"Graph Theory","author":"R Diestel","year":"2017","unstructured":"Diestel, R.: Graph Theory, 5th edn. Springer Publishing Company, Incorporated (2017)","edition":"5"},{"key":"782_CR26","doi-asserted-by":"publisher","unstructured":"D\u00f6ring, S., Marx, D., Wellnitz, P.: Counting small induced subgraphs with edge-monotone properties. CoRR, (2023). https:\/\/doi.org\/10.48550\/arXiv.2311.08988arxiv:abs\/2311.08988","DOI":"10.48550\/arXiv.2311.08988"},{"issue":"2","key":"782_CR27","doi-asserted-by":"publisher","first-page":"248","DOI":"10.1145\/321694.321699","volume":"19","author":"J Edmonds","year":"1972","unstructured":"Edmonds, J., Karp, R.M.: Theoretical improvements in algorithmic efficiency for network flow problems. J. ACM 19(2), 248\u2013264 (1972). https:\/\/doi.org\/10.1145\/321694.321699","journal-title":"J. ACM"},{"key":"782_CR28","unstructured":"Eiben, E., Knop, D., Panolan, F., Such\u00fd, O.: Complexity of the Steiner network problem with respect to the number of terminals. CoRR, abs\/1802.08189, (2018). arXiv:1802.08189"},{"key":"782_CR29","doi-asserted-by":"crossref","unstructured":"Eppstein, D.: Diameter and treewidth in minor-closed graph families. Algorithmica, 27:275\u2013291, (1999). URL: https:\/\/api.semanticscholar.org\/CorpusID:3172160","DOI":"10.1007\/s004530010020"},{"key":"782_CR30","unstructured":"Eppstein, D.: Dynamic generators of topologically embedded graphs. In: Proceedings of the Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms, January 12-14, 2003, Baltimore, Maryland, USA, pages 599\u2013608. ACM\/SIAM, (2003). URL: http:\/\/dl.acm.org\/citation.cfm?id=644108.644208"},{"key":"782_CR31","unstructured":"Eppstein, D., Lokshtanov, D.: The parameterized complexity of finding point sets with hereditary properties. CoRR, abs\/1808.02162, (2018). arXiv:1808.02162"},{"issue":"7","key":"782_CR32","doi-asserted-by":"publisher","first-page":"1989","DOI":"10.1007\/s00453-020-00683-w","volume":"82","author":"AE Feldmann","year":"2020","unstructured":"Feldmann, A.E., Marx, D.: The parameterized hardness of the k-center problem in transportation networks. Algorithmica 82(7), 1989\u20132005 (2020). https:\/\/doi.org\/10.1007\/s00453-020-00683-w","journal-title":"Algorithmica"},{"key":"782_CR33","doi-asserted-by":"publisher","unstructured":"Fomin, F.\u00a0V., Lokshtanov, D., Marx, D., Pilipczuk, M., Pilipczuk, M., Saurabh, S.: Subexponential parameterized algorithms for planar and apex-minor-free graphs via low treewidth pattern covering. In: Dinur, I. editor, IEEE 57th Annual Symposium on Foundations of Computer Science, FOCS 2016, 9-11 October 2016, Hyatt Regency, New Brunswick, New Jersey, USA, pages 515\u2013524. IEEE Computer Society, (2016). https:\/\/doi.org\/10.1109\/FOCS.2016.62","DOI":"10.1109\/FOCS.2016.62"},{"key":"782_CR34","doi-asserted-by":"publisher","first-page":"399","DOI":"10.4153\/CJM-1956-045-5","volume":"8","author":"LR Ford","year":"1956","unstructured":"Ford, L.R., Fulkerson, D.R.: Maximal flow through a network. Can. J. Math. 8, 399\u2013404 (1956). https:\/\/doi.org\/10.4153\/CJM-1956-045-5","journal-title":"Can. J. Math."},{"key":"782_CR35","doi-asserted-by":"publisher","unstructured":"Galby, E., Kisfaludi-Bak, S., Marx, D., Sharma, R.: Subexponential parameterized directed Steiner network problems on planar graphs: a complete classification. CoRR, abs\/2208.06015, (2022). https:\/\/doi.org\/10.48550\/arXiv.2208.06015","DOI":"10.48550\/arXiv.2208.06015"},{"issue":"1","key":"782_CR36","doi-asserted-by":"publisher","first-page":"89","DOI":"10.1007\/s00453-012-9685-8","volume":"67","author":"J Guo","year":"2013","unstructured":"Guo, J., Hartung, S., Niedermeier, R., Such\u00fd, O.: The parameterized complexity of local search for tsp, more refined. Algorithmica 67(1), 89\u2013110 (2013). https:\/\/doi.org\/10.1007\/s00453-012-9685-8","journal-title":"Algorithmica"},{"issue":"3","key":"782_CR37","doi-asserted-by":"publisher","first-page":"344","DOI":"10.1287\/opre.11.3.344","volume":"11","author":"TC Hu","year":"1963","unstructured":"Hu, T.C.: Multi-commodity network flows. Oper. Res. 11(3), 344\u2013360 (1963)","journal-title":"Oper. Res."},{"issue":"4","key":"782_CR38","doi-asserted-by":"publisher","first-page":"512","DOI":"10.1006\/jcss.2001.1774","volume":"63","author":"R Impagliazzo","year":"2001","unstructured":"Impagliazzo, R., Paturi, R., Zane, F.: Which problems have strongly exponential complexity? J. Comput. Syst. Sci. 63(4), 512\u2013530 (2001). https:\/\/doi.org\/10.1006\/jcss.2001.1774","journal-title":"J. Comput. Syst. Sci."},{"issue":"1","key":"782_CR39","doi-asserted-by":"publisher","first-page":"39","DOI":"10.1016\/j.jcss.2012.04.004","volume":"79","author":"K Jansen","year":"2013","unstructured":"Jansen, K., Kratsch, S., Marx, D., Schlotter, I.: Bin packing with fixed number of bins revisited. J. Comput. Syst. Sci. 79(1), 39\u201349 (2013). https:\/\/doi.org\/10.1016\/j.jcss.2012.04.004","journal-title":"J. Comput. Syst. Sci."},{"issue":"2","key":"782_CR40","doi-asserted-by":"publisher","first-page":"1294","DOI":"10.1137\/15M103618X","volume":"31","author":"M Jones","year":"2017","unstructured":"Jones, M., Daniel Lokshtanov, M.S., Ramanujan, S.S., Such\u00fd, O.: Parameterized complexity of directed Steiner tree on sparse graphs. SIAM J. Discrete Math. 31(2), 1294\u20131327 (2017). https:\/\/doi.org\/10.1137\/15M103618X","journal-title":"SIAM J. Discrete Math."},{"key":"782_CR41","doi-asserted-by":"publisher","unstructured":"Karthik, C. S., Marx, D., Pilipczuk, M., Souza, U.\u00a0S.: Conditional lower bounds for sparse parameterized 2-CSP: A streamlined proof. CoRR, abs\/2311.05913, (2023). https:\/\/doi.org\/10.48550\/arXiv.2311.05913","DOI":"10.48550\/arXiv.2311.05913"},{"key":"782_CR42","doi-asserted-by":"publisher","unstructured":"Kawarabayashi, K., Mohar, B., Reed, B.\u00a0A.: A simpler linear time algorithm for embedding graphs into an arbitrary surface and the genus of graphs of bounded tree-width. In: 49th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2008, October 25-28, 2008, Philadelphia, PA, USA, pages 771\u2013780. IEEE Computer Society, (2008). https:\/\/doi.org\/10.1109\/FOCS.2008.53","DOI":"10.1109\/FOCS.2008.53"},{"key":"782_CR43","doi-asserted-by":"publisher","unstructured":"Klein, P.\u00a0N., Marx, D.: Solving planar $$k$$-terminal cut in $${O}(n^{c\\sqrt{k}})$$ time. In: Czumaj, A., Mehlhorn, K., Pitts, A.\u00a0M., Wattenhofer, R. editors, Automata, Languages, and Programming - 39th International Colloquium, ICALP 2012, Warwick, UK, July 9-13, 2012, Proceedings, Part I, volume 7391 of Lecture Notes in Computer Science, pages 569\u2013580. Springer, (2012). https:\/\/doi.org\/10.1007\/978-3-642-31594-7_48","DOI":"10.1007\/978-3-642-31594-7_48"},{"key":"782_CR44","doi-asserted-by":"publisher","unstructured":"Klein, P.\u00a0N., Marx, D.: A subexponential parameterized algorithm for subset TSP on planar graphs. In: Chekuri, C. editor, Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2014, Portland, Oregon, USA, January 5-7, 2014, pages 1812\u20131830. SIAM, (2014). https:\/\/doi.org\/10.1137\/1.9781611973402.131","DOI":"10.1137\/1.9781611973402.131"},{"key":"782_CR45","doi-asserted-by":"publisher","unstructured":"Lokshtanov, D., Ramanujan, M.\u00a0S., Saurabh, S., Zehavi, M.: Parameterized complexity and approximability of directed odd cycle transversal. In: Chawla, S. editor, Proceedings of the 2020 ACM-SIAM Symposium on Discrete Algorithms, SODA 2020, Salt Lake City, UT, USA, January 5-8, 2020, pages 2181\u20132200. SIAM, (2020). https:\/\/doi.org\/10.1137\/1.9781611975994.134","DOI":"10.1137\/1.9781611975994.134"},{"key":"782_CR46","doi-asserted-by":"publisher","unstructured":"Lokshtanov, D., Saurabh, S., Wahlstr\u00f6m, M.: Subexponential parameterized odd cycle transversal on planar graphs. In: D\u2019Souza, D., Kavitha, T., Radhakrishnan, J. editors, IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, FSTTCS 2012, December 15-17, 2012, Hyderabad, India, volume\u00a018 of LIPIcs, pages 424\u2013434. Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik, (2012). https:\/\/doi.org\/10.4230\/LIPIcs.FSTTCS.2012.424","DOI":"10.4230\/LIPIcs.FSTTCS.2012.424"},{"key":"782_CR47","doi-asserted-by":"publisher","unstructured":"Marx, D.: Parameterized complexity of independence and domination on geometric graphs. In Bodlaender, H.\u00a0L., Langston, M.\u00a0A. editors, Parameterized and Exact Computation, Second International Workshop, IWPEC 2006, Z\u00fcrich, Switzerland, September 13-15, 2006, Proceedings, volume 4169 of Lecture Notes in Computer Science, pages 154\u2013165. Springer, (2006). https:\/\/doi.org\/10.1007\/11847250_14","DOI":"10.1007\/11847250_14"},{"issue":"1","key":"782_CR48","doi-asserted-by":"publisher","first-page":"85","DOI":"10.4086\/toc.2010.v006a005","volume":"6","author":"D Marx","year":"2010","unstructured":"Marx, D.: Can you beat treewidth? Theory Comput. 6(1), 85\u2013112 (2010). https:\/\/doi.org\/10.4086\/toc.2010.v006a005","journal-title":"Theory Comput."},{"key":"782_CR49","doi-asserted-by":"publisher","unstructured":"Marx, D.: A tight lower bound for planar multiway cut with fixed number of terminals. In Czumaj, A., Mehlhorn, K., Pitts, A.\u00a0M., Wattenhofer, R. editors, Automata, Languages, and Programming - 39th International Colloquium, ICALP 2012, Warwick, UK, July 9-13, 2012, Proceedings, Part I, volume 7391 of Lecture Notes in Computer Science, pages 677\u2013688. Springer, (2012). https:\/\/doi.org\/10.1007\/978-3-642-31594-7_57","DOI":"10.1007\/978-3-642-31594-7_57"},{"key":"782_CR50","doi-asserted-by":"publisher","unstructured":"Marx, D\u00e1niel, Pilipczuk, Marcin, Pilipczuk, Michal: On subexponential parameterized algorithms for Steiner tree and directed subset TSP on planar graphs. In Mikkel Thorup, editor, 59th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2018, Paris, France, October 7-9, 2018, pages 474\u2013484. IEEE Computer Society, (2018). https:\/\/doi.org\/10.1109\/FOCS.2018.00052","DOI":"10.1109\/FOCS.2018.00052"},{"issue":"2","key":"782_CR51","doi-asserted-by":"publisher","first-page":"13:1","DOI":"10.1145\/3483425","volume":"18","author":"D. Marx","year":"2022","unstructured":"Marx, D.., Pilipczuk, M..: Optimal parameterized algorithms for planar facility location problems using Voronoi diagrams. ACM Trans. Algorithms 18(2), 13:1-13:64 (2022). https:\/\/doi.org\/10.1145\/3483425","journal-title":"ACM Trans. Algorithms"},{"issue":"1","key":"782_CR52","doi-asserted-by":"publisher","first-page":"6","DOI":"10.1137\/S089548019529248X","volume":"12","author":"B Mohar","year":"1999","unstructured":"Mohar, B.: A linear time algorithm for embedding graphs in an arbitrary surface. SIAM J. Discret. Math. 12(1), 6\u201326 (1999). https:\/\/doi.org\/10.1137\/S089548019529248X","journal-title":"SIAM J. Discret. Math."},{"key":"782_CR53","doi-asserted-by":"crossref","unstructured":"Mohar, B., Thomassen, C.: Graphs on surfaces. In Johns Hopkins series in the mathematical sciences, (2001). URL: https:\/\/api.semanticscholar.org\/CorpusID:27349785","DOI":"10.56021\/9780801866890"},{"key":"782_CR54","doi-asserted-by":"publisher","unstructured":"Nederlof, J.: Detecting and counting small patterns in planar graphs in subexponential parameterized time. In: Makarychev, K., Makarychev, Y., Tulsiani, M., Kamath, G., Chuzhoy, J. editors, Proccedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing, STOC 2020, Chicago, IL, USA, June 22-26, 2020, pages 1293\u20131306. ACM, 2020. https:\/\/doi.org\/10.1145\/3357713.3384261","DOI":"10.1145\/3357713.3384261"},{"key":"782_CR55","doi-asserted-by":"publisher","unstructured":"Pandey, S., van Leeuwen, E.\u00a0J.: Planar Multiway Cut with Terminals on Few Faces, pages 2032\u20132063. URL: https:\/\/epubs.siam.org\/doi\/abs\/10.1137\/1.9781611977073.81, https:\/\/doi.org\/10.1137\/1.9781611977073.81","DOI":"10.1137\/1.9781611977073.81"},{"key":"782_CR56","unstructured":"Parsons, T.\u00a0D., Pica, G., Pisanski, T., Ventre, A. G.\u00a0S.: Orientably simple graphs. Mathematica Slovaca, 37(4):391\u2013394, (1987). URL: http:\/\/eudml.org\/doc\/31798"},{"key":"782_CR57","doi-asserted-by":"publisher","unstructured":"Philip, G., Raman, V., Sikdar, S.: Polynomial kernels for dominating set in graphs of bounded degeneracy and beyond. ACM Trans. Algorithms, 9(1), (December 2012). https:\/\/doi.org\/10.1145\/2390176.2390187","DOI":"10.1145\/2390176.2390187"},{"issue":"3","key":"782_CR58","doi-asserted-by":"publisher","first-page":"13:1","DOI":"10.1145\/3201775","volume":"10","author":"M. Pilipczuk","year":"2018","unstructured":"Pilipczuk, M.., Wahlstr\u00f6m, Magnus: Directed multicut is W[1]-hard, even for four terminal pairs. TOCT 10(3), 13:1-13:18 (2018). https:\/\/doi.org\/10.1145\/3201775","journal-title":"TOCT"},{"issue":"3","key":"782_CR59","doi-asserted-by":"publisher","first-page":"370","DOI":"10.1016\/0095-8956(79)90012-1","volume":"26","author":"PD Seymour","year":"1979","unstructured":"Seymour, P.D.: A short proof of the two-commodity flow theorem. J. Comb. Theory, Ser. B, 26(3), 370\u2013371 (1979). https:\/\/doi.org\/10.1016\/0095-8956(79)90012-1","journal-title":"J. Comb. Theory, Ser. B,"},{"key":"782_CR60","doi-asserted-by":"publisher","unstructured":"van\u00a0den Brand, J., Chen, L., Kyng, R., Liu, Y.\u00a0P., Peng, R., Gutenberg, M.\u00a0P., Sachdeva, S., Sidford, A.: A deterministic almost-linear time algorithm for minimum-cost flow. CoRR, abs\/2309.16629, 2023. https:\/\/doi.org\/10.48550\/arXiv.2309.16629","DOI":"10.48550\/arXiv.2309.16629"},{"key":"782_CR61","doi-asserted-by":"publisher","unstructured":"van\u00a0den Brand, J., Gao, Y., Jambulapati, A., Lee, Y.\u00a0T., Liu, Y.\u00a0P., Peng, R., Sidford, A.: Faster maxflow via improved dynamic spectral vertex sparsifiers. In Stefano Leonardi and Anupam Gupta, editors, STOC \u201922: 54th Annual ACM SIGACT Symposium on Theory of Computing, Rome, Italy, June 20 - 24, (2022), pages 543\u2013556. ACM, 2022. https:\/\/doi.org\/10.1145\/3519935.3520068","DOI":"10.1145\/3519935.3520068"}],"container-title":["Discrete & Computational Geometry"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00454-025-00782-x.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00454-025-00782-x","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00454-025-00782-x.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,3,2]],"date-time":"2026-03-02T14:49:54Z","timestamp":1772462994000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00454-025-00782-x"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,10,22]]},"references-count":61,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2026,3]]}},"alternative-id":["782"],"URL":"https:\/\/doi.org\/10.1007\/s00454-025-00782-x","relation":{},"ISSN":["0179-5376","1432-0444"],"issn-type":[{"value":"0179-5376","type":"print"},{"value":"1432-0444","type":"electronic"}],"subject":[],"published":{"date-parts":[[2025,10,22]]},"assertion":[{"value":"7 October 2024","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"21 September 2025","order":2,"name":"revised","label":"Revised","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"22 September 2025","order":3,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"22 October 2025","order":4,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}