Multicut Problems in Almost-Planar Graphs: The Dependency of Complexity on the Demand Pattern

Florian Hörsch, Dániel Marx

Given a graph $G$, a set $T$ of terminal vertices, and a demand graph $H$ on $T$, the \textsc{Multicut} problem asks for a set of edges of minimum weight that separates the pairs o…