## Abstract

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 language | English (US) |
---|---|

Pages (from-to) | 261-271 |

Number of pages | 11 |

Journal | SIAM Journal on Discrete Mathematics |

Volume | 20 |

Issue number | 1 |

DOIs | |

State | Published - 2006 |

Externally published | Yes |

## Keywords

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

## ASJC Scopus subject areas

- General Mathematics