On a bidirected relaxation for the MULTIWAY CUT problem

Chandra Chekuri, Anupam Gupta, Amit Kumar

Abstract

In the MULTIWAY CUT problem, we are given an undirected edge-weighted graph G = ( V , E ) with c e denoting the cost (weight) of edge e. We are also given a subset S of V, of size k, called the terminals. The objective is to find a minimum cost set of edges whose removal ensures that the terminals are disconnected. In this paper, we study a bidirected linear programming relaxation of MULTIWAY CUT. We resolve an open problem posed by Vazirani [Approximation Algorithms, first ed., Springer, Berlin, Heidelberg, 2001], and show that the integrality gap of this relaxation is not better than that for a geometric linear programming relaxation given by Caˇlinescu et al. [J. Comput. System Sci. 60(3) (2000) 564–574], and may be strictly worse on some instances.
BibTeX
@article{chekuri2005bidirected,
  author = {Chandra Chekuri and Anupam Gupta and Amit Kumar},
  title = {{On a bidirected relaxation for the MULTIWAY CUT problem}},
  journal = {Discret. Appl. Math.},
  year = {2005},
  doi = {10.1016/j.dam.2005.04.003},
}

Loading related content...

Figure