# Multicut Problems in Embedded Graphs: The Dependency of Complexity on the Demand Pattern

conference contribution

posted on 2024-10-30, 16:51 authored by Jacob FockeJacob Focke, Florian HörschFlorian Hörsch, Shaohua Li, Dániel MarxDániel MarxThe 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.

## History

## Name of Conference

International Symposium on Computational Geometry (SoCG)## BibTeX

@conference{Focke:Hörsch:Li:Marx:2024, title = "Multicut Problems in Embedded Graphs: The Dependency of Complexity on the Demand Pattern", author = "Focke, jacob" AND "Hörsch, Florian" AND "Li, Shaohua" AND "Marx, Dániel", year = 2024, month = 6, doi = "10.4230/LIPIcs.SoCG.2024.57" }## Usage metrics

## Categories

No categories selected## Licence

## Exports

RefWorks

BibTeX

Ref. manager

Endnote

DataCite

NLM

DC