MINIMUM MULTI-CUT

• INSTANCE: A graph $G=\left(V,E\right)$, a set $S \subseteq V\times V$ of source-terminal pairs, and a weight function $w : E \rightarrow N$.

• SOLUTION: A multi-cut, i.e., a set $E'\subseteq E$ such that the removal of E' from E disconnects $s_i$ from $t_i$ for every pair $(s_i,t_i)\in S$.

• MEASURE: The weight of the cut, i.e., $\sum_{e \in E'}w(e)$.

  
  

• Good News: Approximable within $O(\log \vert S\vert)$ [189]

• Bad News: APX-hard.
• Comment: Generalization of MINIMUM MULTIWAY CUT. When the graph is a tree the problem is approximable within 2 and is APX-complete even for trees of height one and unit edge weight [190]. The variation in which vertices instead of edges should be deleted is also approximable within $O(\log \vert S\vert)$ [188]. The variation in which the input specifies a set of demand edges and a given node $v^{*}$ and the solution must be a feasible $v^{*}$-cut, i.e., the demand edges must either be in the cut or have both endpoints on the opposite part of $v^{*}$ is approximable within 2.8 [473].