Algorithms & Randomness Center (ARC)

Vivek Madan(UIUC)

Monday, February 19, 2018

Klaus 1116 East – 11:00 am

Title:  Approximating Multicut and the Demand graph

Abstract:  The Multicut problem is a generalization of the classical $s-t$ cut problem to multiple pairs. Given an edge-weighted directed or undirected supply graph G=(V,E), and k source-sink pairs (s1,t1),\dots,(sk,tk), the goal is to remove a minimum weight subset of edges in G such that all the given (si,ti) pairs are disconnected. Over the past 30 years, Multicut has attracted significant attention in approximation algorithms, and a variety of results have been obtained for general and special classes of supply graphs. Motivated by new applications, I study Multicut with a focus on the demand graph (graph with an edge set {(si,ti) \mid i \in [k]}). We obtain several new approximability and inapproximability results based on a labeling viewpoint of the problem.

1.        Approximation algorithms: We present a unified 2-approximation algorithm for undirected multicut problem for tK2-free demand graphs when t is a fixed constant. For directed multiway cut we significantly simplify the 2-approximation algorithm of Naor and Zosin from twenty years ago; our rounding strategy yields a constant factor for much more general classes of demand graphs. For the problem of linear-k-cut (a special case of directed multicut which motivated this work), we show some initial results and prove a tight \sqrt{2}-approximation algorithm when k=3.

2.        Hardness of approximation: We prove that for a class of demand graphs, undirected multicut admits a constant factor approximation algorithm iff the class is tK2-free for some constant t. For directed multicut, we prove that assuming the Unique Games Conjecture (UGC), hardness of approximation matches the flow-cut gap for any fixed bi-partite demand graph. As a consequence, we prove that for any fixed k \ge 2, there is no (k-eps) approximation algorithm for Multicut with k pairs, assuming UGC.

----------------------------------

Speaker's Webpage

Videos of recent talks are available at: https://smartech.gatech.edu/handle/1853/46836

Click here to subscribe to the seminar email list: arc-colloq@cc.gatech.edu