2OPT Approximation Algorithm for Multiway Cut Problem
Minimum $k$-Multiway Cut

Given a graph $G =(V,E)$ and a set of terminals $S=\{s_1, s_2, \dotsc, s_k\} \subseteq V$ find a minimum set of edges $E' \subseteq E$ whose removal separates each pair of terminals in $S$.

Case when $k=2$

For the case when $k=2$ Minimum $k$-Multiway cut is exactly the Minimum $s$-$t$ Cut problem. To see this simply let $(s_1, s_2) = (s,t)$ and compute a min $s$-$t$ cut. This can be solved in polynomial time by various Maximum-Flow algorithms.

Case when $k \geq 3$

We can design a very simple 2OPT approximation algorithm for the $k$-Multiway Cut problem. For each $s_i$, where $1 \leq i \leq k$, collapse $S \setminus \{s_i\}$ into a single node $t_i$. Compute a min $s_i$-$t_i$ cut and call it $C_i$. Repeat this for each possible $s_i$. Output  $C = \bigcup_{i=1}^k C_i$.

Claim: $|C| \leq 2 \textrm{OPT}$

Let $A$ be the optimal multiway cut and let $A_i$ be a cut that separates $s_i$ from the rest of the graph. Since each edge in $A$ is adjacent to 2 components, each edge must be in two of the cuts $A_i$. Hence, $$\begin{align*}&amp;\sum_i |A_i| = 2|A| &amp;(*)\end{align*}.$$ Further, since $C_i$ is a minimal cut, $|C_i| \leq |A_i|$. This fact together with $(*)$ implies that our algorithm achieves a $2\mathrm{OPT}$ approximation ratio.

Claim: $\text{Proposed algorithm runs in polynomial time}$

The algorithm requires $k$ calls to a Minimum $s$-$t$ cut procedure. Since we only make a constant number of calls to a polynomial-time algorithm, our resulting algorithm is still polynomial.

You can further improve this to $(2 - \frac{2}{k})\mathrm{OPT}$ by dropping the heaviest cut. Beating that bound requires a slightly more advanced LP rounding schema.