## Abstract

We study the multiway cut problem in directed graphs and one of its special cases, the node-weighted multiway cut problem in undirected graphs. In Directed Multiway Cut (Dir-MC) the input is an edge-weighted directed graph G = {V,E) and a set of k terminal nodes {s_{1}, S_{2},..., S_{k} } ⊆ V; the goal is to find a min-weight subset of edges whose removal ensures that there is no path from S_{i} to S_{j} for any i ≠ j. In Node-weighted Multiway Cut (Node-wt-MC) the input is a node-weighted undirected graph G and a set of k terminal nodes {s_{1}, S_{2},..., s_{k}} ⊆V; the goal is to find a min-weight subset of nodes whose removal ensures that there is no path from S_{i} to S_{j} for any i ≠ j. DlR-MC admits a 2-approximation [28] and node-wt-MC admits a 2(1-1/k)-approximation [21], both via rounding of LP relaxations. Previous rounding algorithmms for these problems, from nearly twenty years ago, are based on careful rounding of an optimum solution to an LP relaxation. This is particularly true for DlR-MC for which the rounding relies on a custom LP formulation instead of the natural distance based LP relaxation [28]. In this paper we describe extremely simple and near linear-time rounding algorithms for DlR-MC and Node-wt-MC via a natural distance based LP relaxation. The dual of this relaxation is a special case of the maximum multicommodity flow problem. Our algorithms achieve the same bounds as before but have the significant advantage in that they can work with any feasible solution to the relaxation. Consequently, in addition to obtaining "book" proofs of LP rounding for these two basic problems, we also obtain significantly faster approximation algorithms by taking advantage of known algorithms for computing near-optimal solutions for maximum multicommodity flow problems. We also investigate lower bounds for DlR-MC when k = 2 and prove that the integrality gap of the LP relaxation is 2 even in planar directed graphs.

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

Title of host publication | 27th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2016 |

Editors | Robert Krauthgamer |

Publisher | Association for Computing Machinery |

Pages | 797-807 |

Number of pages | 11 |

ISBN (Electronic) | 9781510819672 |

DOIs | |

State | Published - 2016 |

Event | 27th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2016 - Arlington, United States Duration: Jan 10 2016 → Jan 12 2016 |

### Publication series

Name | Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms |
---|---|

Volume | 2 |

### Other

Other | 27th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2016 |
---|---|

Country/Territory | United States |

City | Arlington |

Period | 1/10/16 → 1/12/16 |

## ASJC Scopus subject areas

- Software
- General Mathematics