A Near-Linear Approximation Scheme for Multicuts of Embedded Graphs with a Fixed Number of Terminals

Vincent Cohen-Addad, Éric Colin de Verdière, Arnaud de Mesmay

For an undirected edge-weighted graph $G$ and a set $R$ of pairs of vertices called pairs of terminals, a multicut is a set of edges such that removing these edges from $G$ disconn…