Simple and fast rounding algorithms for directed and node-weighted multiway cut

Chandra Chekuri, Vivek Madan

Research output: Chapter in Book/Report/Conference proceedingConference contribution

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 {s1, S2,..., Sk } ⊆ V; the goal is to find a min-weight subset of edges whose removal ensures that there is no path from Si to Sj 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 {s1, S2,..., sk} ⊆V; the goal is to find a min-weight subset of nodes whose removal ensures that there is no path from Si to Sj 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 languageEnglish (US)
Title of host publication27th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2016
EditorsRobert Krauthgamer
PublisherAssociation for Computing Machinery
Pages797-807
Number of pages11
ISBN (Electronic)9781510819672
DOIs
StatePublished - 2016
Event27th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2016 - Arlington, United States
Duration: Jan 10 2016Jan 12 2016

Publication series

NameProceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms
Volume2

Other

Other27th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2016
Country/TerritoryUnited States
CityArlington
Period1/10/161/12/16

ASJC Scopus subject areas

  • Software
  • Mathematics(all)

Fingerprint

Dive into the research topics of 'Simple and fast rounding algorithms for directed and node-weighted multiway cut'. Together they form a unique fingerprint.

Cite this