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

Jacob Focke, Florian Hörsch, Shaohua Li +1

The Multicut problem asks for a minimum cut separating certain pairs of vertices: formally, given a graph $G$ and demand graph $H$ on a set $T\subseteq V(G)$ of terminals, the task…