<p>Currently the best approximation algorithm for the MULTIWAY CUT problem is obtained via the linear program based on geometrical embedding by CKR [1].  Let $U_i$ be those vertices in $V-T$ which is assigned $e_i = \{0, \dots, 1, \dots, 0\}$, that is, $1$ at the $i$-th coordinate and $0$ at all others.  My question is: <strong>is there always an optimal solution that keeps vertices $U_i$ with $t_i$</strong> (the $i$-th terminal)?</p>

<p><strong>Remark.</strong> For the multicommodity-flow-based linear program for the MULTIWAY CUT problem (see [2]), it is not hard to show the existence of an optimal solution.  It should be verified with the similar idea as [3], which proves the existence of such an optimal solution on the NODE MULTIWAY CUT problem.</p>

<ol>
<li>Calinescu, G., H. Karloff, Y. Rabani. 2000. An improved approximation algorithm for Multiway Cut. <em>J. Comput. System Sci.</em> 60(3) 564–574.</li>
<li>E. Dahlhaus, D. S. Johnson, C. H. Papadimitriou, P. D. Seymour, and M. Yannakakis, The complexity of multiterminal cuts, <em>SIAM J. Comput</em>. 23 (1994), 864894. [Preliminary version appeared in STOC '92]</li>
<li>Sylvain Guillemot, FPT algorithms for path-transversal and cycle-transversal problems, <em>Discrete Optimization</em> 8 (2011) 61–71</li>
</ol>

<p>P.S. I'm aware of Karger's result, but that is irrelevant.</p>

CC BY-SA 3.0
2012-04-19T22:34:31.163Z
As a (maybe) independent and general question: Let (IP) be an 0-1 IP, and (LP) be its relaxation.  Fixing an optimal solution $X$ for (LP), denote by $X^1$ the set of variables which are assigned $1$, then the question is: Is there always an optimal solution $X'$ to (IP) which also assgins $1$ to variables in $X^1$?
Yixin Cao
CC BY-SA 3.0
2012-04-22T20:36:17.700Z
The answer to your general question is no. Take the max weight matching problem in general graphs and the simple IP which has a variable $x(e)$ for each edge $e$ and a constraint at each vertex $\sum_{e \in \delta(v)} x(e) \leq 1$. The LP relaxation for this is not integral in non-bipartite graphs. Take the graph consisting of a triangle $v_1,v_2,v_3$ with a path $v_3,v_4,v_5$ attached to $v_3$. If triangle edges are $10$, $v_3v_4$ weight is $2$ and $v_4v_5$ weight is $1$ then optimal IP solution is to take $v_1v_2$ and $v_3v_4$. Optimal LP soln is $1$ on $v_4v_5$ and $1/2$ on triangle edges.
Chandra Chekuri
<ds.algorithms><approximation-algorithms><linear-programming><multicommodity-flow>
On the optimal solution of the CKR formulation for MULTIWAY CUT
Yixin Cao
# On the optimal solution of the CKR formulation for MULTIWAY CUT

(Asked by: username_0 on 2012-04-19)

Currently the best approximation algorithm for the MULTIWAY CUT problem is obtained via the linear program based on geometrical embedding by CKR [1]. Let $U\_i$ be those vertices in $V-T$ which is assigned $e\_i = \{0, \dots, 1, \dots, 0\}$, that is, $1$ at the $i$-th coordinate and $0$ at all others. My question is: **is there always an optimal solution that keeps vertices $U\_i$ with $t\_i$** (the $i$-th terminal)?

**Remark.** For the multicommodity-flow-based linear program for the MULTIWAY CUT problem (see [2]), it is not hard to show the existence of an optimal solution. It should be verified with the similar idea as [3], which proves the existence of such an optimal solution on the NODE MULTIWAY CUT problem.

1. Calinescu, G., H. Karloff, Y. Rabani. 2000. An improved approximation algorithm for Multiway Cut. *J. Comput. System Sci.* 60(3) 564–574.
2. E. Dahlhaus, D. S. Johnson, C. H. Papadimitriou, P. D. Seymour, and M. Yannakakis, The complexity of multiterminal cuts, *SIAM J. Comput*. 23 (1994), 864894. [Preliminary version appeared in STOC '92]
3. Sylvain Guillemot, FPT algorithms for path-transversal and cycle-transversal problems, *Discrete Optimization* 8 (2011) 61–71

P.S. I'm aware of Karger's result, but that is irrelevant.

**Tags:** ds.algorithms, approximation-algorithms, linear-programming, multicommodity-flow

> **Comments:**
> **username_0**: As a (maybe) independent and general question: Let (IP) be an 0-1 IP, and (LP) be its relaxation.  Fixing an optimal solution $X$ for (LP), denote by $X^1$ the set of variables which are assigned $1$, then the question is: Is there always an optimal solution $X'$ to (IP) which also assgins $1$ to variables in $X^1$?  
> **username_1**: The answer to your general question is no. Take the max weight matching problem in general graphs and the simple IP which has a variable $x(e)$ for each edge $e$ and a constraint at each vertex $\sum_{e \in \delta(v)} x(e) \leq 1$. The LP relaxation for this is not integral in non-bipartite graphs. Take the graph consisting of a triangle $v_1,v_2,v_3$ with a path $v_3,v_4,v_5$ attached to $v_3$. If triangle edges are $10$, $v_3v_4$ weight is $2$ and $v_4v_5$ weight is $1$ then optimal IP solution is to take $v_1v_2$ and $v_3v_4$. Optimal LP soln is $1$ on $v_4v_5$ and $1/2$ on triangle edges.  

---

## 0 answers

