On a bidirected relaxation for the MULTIWAY CUT problem

Chandra Chekuri, Anupam Gupta, Amit Kumar

Research output: Contribution to journalArticlepeer-review


In the MULTIWAY CUT problem, we are given an undirected edge-weighted graph G=(V,E) with ce 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 Cǎlinescu et al. [J. Comput. System Sci. 60(3) (2000) 564-574], and may be strictly worse on some instances.

Original languageEnglish (US)
Pages (from-to)67-79
Number of pages13
JournalDiscrete Applied Mathematics
Issue number1-3
StatePublished - Sep 1 2005


  • Approximation algorithm
  • Bidirected relaxation
  • Integrality gap
  • MULTIWAY CUT problem

ASJC Scopus subject areas

  • Discrete Mathematics and Combinatorics
  • Applied Mathematics


Dive into the research topics of 'On a bidirected relaxation for the MULTIWAY CUT problem'. Together they form a unique fingerprint.

Cite this