Question

In the MULTIWAY CUT problem, the input is an undirected graph$\mathit{G}\mathbf{=}\left(V,E\right)$ and a set of terminal nodes$\mathit{s}\mathbf{1}\mathbf{,}\mathit{s}\mathbf{2}\mathbf{,}\mathbf{.}\mathbf{.}\mathbf{.}\mathbf{,}\mathit{s}\mathit{k}\mathbf{\in }\mathit{V}\mathbf{.}$ The goal is to find the minimum set of edges in whose removal leaves all terminals in different components.

(a) Show that this problem can be solved exactly in polynomial time when $\mathit{k}\mathbf{=}\mathbf{2}\mathbf{.}$

(b) Give an approximation algorithm with ratio at most$\mathbf{2}$ for the case $\mathbf{k}\mathbf{=}\mathbf{3}\mathbf{.}$

(c) Design a local search algorithm for multiway cut.

Short answer

AMULTIWAY CUT problem can be solved exactly in polynomial time when the value of k is equals to two is proved.

b). Anapproximation algorithm is proved where the ratio at most two for the case $k=3.$

c). Alocal search algorithm for multiway cut is given below.

Step-by-step solution

MULTIWAY CUT problem

In the multiway cut problem, we are given a graph$G=\left(V,E\right)$ with k special vertices $s1,s2,...,sk\in V.$Our goal is to find the smallest set of edges which when removed from the graph disconnect the graph into at least k components where each is in a different component. When $k=2$,

this is exactly the min s-t cut problem, but if$k\ge 3$ the problem becomes . Consider the following algorithm.

Let Fi be the set of edges in the minimum cut with si one one side and all other special vertices on the other side. And output is $F$, the union of all . Also note that this is a multiway cut because removing from isolates in its own component.

MULTIWAY CUT problem can be solved exactly in polynomial time when  

The input is an undirected graph$G=\left(V,E\right)$ and a set of terminal nodes$s1,s2,...,sk\in V.$ And the goal is to evaluate the minimum set of edges in and whose removal leaves all terminals in different components.

We say that S is a local optimum if there is no improving step: for all u∈V , there are more {u, v} edges across the cut than connecting the same side. Note that the algorithm outputs a local optimum by definition.

Suppose is a local OPT.

Let across() denote the number of edges incident on u that cross the cut. The since S is a local optimum, we know that

$\begin{array}{l}\left|E\left(S,S\text{'}\right)\right|=\frac{1}{2}\sum u\in V\left(d\left(u\right)\right)\ge \frac{1}{2}X\sum u\in V.\\ d\left(u\right)=14Xu\in V\frac{1}{2}d\left(u\right)=\frac{1}{4}·2m=m/2\end{array}$

Where, $\text{m=}\left|\text{E}\right|\text{.}$

We know and hence the algorithm is a two-approximation.

Note: this is not the best-known approximation for Max-Cut. When we talk about semi definite relaxations, we’ll see the best-known algorithm.

A MULTIWAY CUT problem can be solved exactly in polynomial time when the value of k is equals to two is proved.

Approximation algorithm with ratio at most two for the case  

Give an approximation algorithm with ratio at most two for the case $k=3.$

In the multiway cut problem, we are given a graph$G=\left(V,E\right)$ with k special vertices $s1,s2,...,sk\in V.$Our goal is to find the smallest set of edges which when removed from the graph disconnect the graph into at least k components where each is in a different component. When $k=2$,

this is exactly the min s-t cut problem, but if$k\ge 3$ the problem becomes $NP-hard$. Consider the following algorithm.

Let Fi be the set of edges in the minimum cut with si one one side and all other special vertices on the other side. And output is $F$, the union of all . Also note that this is a multiway cut because removing from$G$ isolates in its own component.

this is exactly the min s-t cut problem, but if$k\ge 3$ the problem becomes $NP-hard$. Consider the following algorithm.

Let Fi be the set of edges in the minimum cut with si one one side and all other special vertices on the other side. And output is $F$, the union of all . Also note that this is a multiway cut because removing from$G$ isolates in its own component.

The approximation algorithm is proved where the ratio at most two for the case$k=3.$

A local search algorithm for multiway cut

Here, a local search algorithm for multiway cut

Sometimes, local search algorithms can give good approximations to NP-hard problems. In the Max-Cut$\left(S,T\right)$problem, we have a graph and want to find a cut with as many edges crossing as possible. One local search algorithm is as follows: Start with any cut, and while some vertex v in S has more neighbors in S than T, we move vertex from$\left(S,T\right)$(we do the same for any vertex $\left(S,T\right)$with more neighbors in $\left(S,T\right)$. Note that any time we move a vertex across the cut, the number of edges crossing the cut increases.

Input: graph$G=\left(V,E\right)$

Output: A set $\text{S}\subseteq \text{V}$

Initialize arbitrarily ,

whilewith more edges to the same side than across do ;

move to the other side;

end while;

return .

there are (this is typical in local search algorithms). We can bound this through some very simple observations.

1. Initially $\left|\text{E}\left(\text{S,S¯}\right)\right|\ge \text{0,}$

2. In every iteration,$\left|\text{E}\left(\text{S,S¯}\right)\right|$ increases by at least one, and

3. $\left|\text{E}\left(\text{S,S¯}\right)\right|$is always at most $m\ll n.$

These facts in the graph$G=\left(V,E\right)$ clearly imply that the number of iterations is at most $m\ll n.$, and thus the total running time is polynomial. To prove the next theorem about the approximation ratio, we will do something which is very common when analyzing local search algorithms. We will not reason directly about the solution which the algorithm outputs,$\left(S,T\right)$ but will instead reason about an arbitrary local optimum. Since the algorithm outputs a local optimum, any bound we can prove which holds for all local optimum will hold for the output of the algorithm.

Hence, a local search algorithm for multiway cut is proved.