MINIMUM MULTIWAY CUT

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

• SOLUTION: A multiway cut, i.e., a set $E'\subseteq E$ such that the removal of E' from E disconnects each terminal from all the others.

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

  
  

• Good News: Approximable within $3/2-1/\vert S\vert$ [95].

• Bad News: APX-complete [131].

• Comment: Admits a PTAS if every vertex has degree $\Theta(\vert V\vert)$ [39]. It remains APX-complete even if $\vert S\vert \geq 3$ is fixed. For $\vert S\vert=4$ and $\vert S\vert=8$ it is approximable within 4/3 and 12/7, respectively. In the case of directed graphs the problem is approximable within 2 [383] and is APX-hard [188]. The vertex deletion variation is approximable within $2-{2}/{\vert S\vert}$ and is APX-complete [188].