## Abstract

We consider the Steiner k-cut problem, which is a common generalization of the k-cut problem and the multiway cut problem: 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 2 - 2/k-approximation based on Gomory-Hu trees, and a 2 - 2/|X|-approximation based on LP rounding. The latter algorithm is based on roundihg a generalization of a linear programming relaxation suggested by Naor and Rabani [8]. The rounding uses the Goemans and Williamson primal-dual algorithm (and analysis) for the Steiner tree problem [4] in an interesting way and differs from the rounding in [8]. We use the insight from the rounding to develop an exact bi-directed formulation for the global minimum cut problem (the k-cut problem with k = 2).

Original language | English (US) |
---|---|

Title of host publication | Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) |

Editors | Jos C. M. Baeten, Jan Karel Lenstra, Joachim Parrow, Gerhard J. Woeginger |

Publisher | Springer |

Pages | 189-199 |

Number of pages | 11 |

ISBN (Print) | 3540404937, 9783540404934 |

DOIs | |

State | Published - 2003 |

Externally published | Yes |

### Publication series

Name | Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) |
---|---|

Volume | 2719 |

ISSN (Print) | 0302-9743 |

ISSN (Electronic) | 1611-3349 |

## Keywords

- K-Cut
- Minimum cut
- Multiway Cut
- Primal-dual
- Steiner tree

## ASJC Scopus subject areas

- Theoretical Computer Science
- General Computer Science