2026-07-18T00:40:12Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:20002 2024-06-06T06:21:16Z ddc:004 open_access

Multicut Problems in Embedded Graphs: The Dependency of Complexity on the Demand Pattern Focke, Jacob Hörsch, Florian Li, Shaohua Marx, Dániel MultiCut Multiway Cut Parameterized Complexity Tight Bounds Embedded Graph Planar Graph Genus Surface Exponential Time Hypothesis The Multicut problem asks for a minimum cut separating certain pairs of vertices: formally, given a graph G and a demand graph H on a set T ⊆ V(G) of terminals, the task is to find a minimum-weight set C of edges of G such that whenever two vertices of T are adjacent in H, they are in different components of G⧵ C. Colin de Verdière [Algorithmica, 2017] showed that Multicut with t terminals on a graph G of genus g can be solved in time f(t,g) n^O(√{g²+gt+t}). Cohen-Addad et al. [JACM, 2021] proved a matching lower bound showing that the exponent of n is essentially best possible (for every fixed value of t and g), even in the special case of Multiway Cut, where the demand graph H is a complete graph. However, this lower bound tells us nothing about other special cases of Multicut such as Group 3-Terminal Cut (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 Multicut can be solved faster than f(t,g) n^{O(√{g²+gt+t})}, and furthermore this is the only property that allows such an improvement. Formally, for a class ℋ of graphs, Multicut(ℋ) is the special case where the demand graph H is in ℋ. For every fixed class ℋ (satisfying some mild closure property), fixed g, and fixed t, our main result gives tight upper and lower bounds on the exponent of n in algorithms solving Multicut(ℋ). In addition, we investigate a similar setting where, instead of parameterizing by the genus g of G, we parameterize by the minimum number k of edges of G that need to be deleted to obtain a planar graph. Interestingly, in this setting it makes a significant difference whether the graph G is weighted or unweighted: further nontrivial algorithmic techniques give substantial improvements in the unweighted case. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Jacob Focke and Florian Hörsch and Shaohua Li and Dániel Marx 2024 Is Part Of LIPIcs, Volume 293, 40th International Symposium on Computational Geometry (SoCG 2024) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.SoCG.2024.57 urn:nbn:de:0030-drops-200021 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2024.57 eng https://creativecommons.org/licenses/by/4.0/legalcode