### Abstract

In the Multiway Cut problem we are given an edge-weighted graph and a subset of the vertices called terminals, and asked for a minimum weight set of edges that separates each terminal from all the others. When the number k of terminals is two, this is simply the min-cut, max-flow problem, and can be solved in polynomial time. We show that the problem becomes NP-hard as soon as κ = 3, but can be solved in polynomial time for planar graphs for any fixed κ. The planar problem is NP-hard, however, if it is not fixed. We also describe a simple approximation algorithm for arbitrary graphs that is guaranteed to come within a factor of 2-2/κ of the optimal cut weight.

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

Title of host publication | Proceedings of the 24th Annual ACM Symposium on Theory of Computing, STOC 1992 |

Publisher | Association for Computing Machinery |

Pages | 241-251 |

Number of pages | 11 |

ISBN (Electronic) | 0897915119 |

DOIs | |

State | Published - Jul 1 1992 |

Event | 24th Annual ACM Symposium on Theory of Computing, STOC 1992 - Victoria, Canada Duration: May 4 1992 → May 6 1992 |

### Publication series

Name | Proceedings of the Annual ACM Symposium on Theory of Computing |
---|---|

Volume | Part F129722 |

ISSN (Print) | 0737-8017 |

### Other

Other | 24th Annual ACM Symposium on Theory of Computing, STOC 1992 |
---|---|

Country | Canada |

City | Victoria |

Period | 5/4/92 → 5/6/92 |

### All Science Journal Classification (ASJC) codes

- Software

## Fingerprint Dive into the research topics of 'The complexity of multiway cuts'. Together they form a unique fingerprint.

## Cite this

*Proceedings of the 24th Annual ACM Symposium on Theory of Computing, STOC 1992*(pp. 241-251). (Proceedings of the Annual ACM Symposium on Theory of Computing; Vol. Part F129722). Association for Computing Machinery. https://doi.org/10.1145/129712.129736