5
$\begingroup$

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.

Improve this question
$\endgroup$
2
  • 1
    $\begingroup$ 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$? $\endgroup$ – Yixin Cao Apr 19 '12 at 22:34
  • $\begingroup$ 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. $\endgroup$ – Chandra Chekuri Apr 22 '12 at 20:36

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.