The Steiner k-cut problem

Chandra Chekuri, Sudipto Guha, Joseph Naor

Research output: Contribution to journalArticlepeer-review


We consider the Steiner k-cut problem which generalizes both the k-cut problem and the multiway cut problem. The Steiner k-cut problem is defined as follows. Given an edge-weighted undirected graph G = (V, E), a subset of vertices X ⊆ V called terminals, and an integer k ≤ |X|, the objective is to find a minimum weight set of edges whose removal results in k disconnected components, each of which contains at least one terminal. We give two approximation algorithms for the problem: a greedy (2 - 2/k)-approximation based on Gomory-Hu trees, and a (2 - 2/|X|)-approximation based on rounding a linear program. We use the insight from the rounding to develop an exact bidirected formulation for the global minimum cut problem (the k-cut problem with k = 2).

Original languageEnglish (US)
Pages (from-to)261-271
Number of pages11
JournalSIAM Journal on Discrete Mathematics
Issue number1
StatePublished - 2006
Externally publishedYes


  • Approximation algorithm
  • Linear program
  • Minimum cut
  • Multiway cut
  • Steiner tree
  • k-cut

ASJC Scopus subject areas

  • General Mathematics


Dive into the research topics of 'The Steiner k-cut problem'. Together they form a unique fingerprint.

Cite this