Approximating k-route cuts

Dec 07, 2011

Place: GHC ~~6501~~ 6115 (note: back to the usual room!)

ABSTRACT:

We study the k-route cut problem: given an undirected edge-weighted graph G=(V,E), a collection {(s_1,t_1),(s_2,t_2),...,(s_r,t_r)} of source-sink pairs, and an integer connectivity requirement k, the goal is to find a minimum-weight subset E' of edges to remove, such that the connectivity of each pair (s_i, t_i) falls below k. Specifically, in the edge-connectivity version, EC-kRC, the requirement is that there are at most (k-1) edge-disjoint paths connecting s_i to t_i in G \ E', while in the vertex-connectivity version, VC-kRC, the same requirement is for vertex-disjoint paths. Prior to our work, poly-logarithmic approximation algorithm has been known for the special case where k=2, but no non-trivial approximation algorithms were known for any value k > 2, except in the single-source setting. We show an O(k log^{3/2}r)-approximation algorithm for EC-kRC with uniform edge weights, and several polylogarithmic bi-criteria approximation algorithms for EC-kRC and VC-kRC, where the connectivity requirement k is violated by a constant factor. Our results improve the previously known result for the case k=2. We also prove that VC-kRC is hard to approximate up to a factor of k^{\epsilon} for some fixed \epsilon > 0.

We then turn to study a simpler version of VC-kRC, where only one source-sink pair is present. We present a simple bi-criteria approximation algorithm for this case. Then we show evidence that even this restricted version of the problem may be hard to approximate. For example, we show that the single source-sink pair version of VC-kRC has no constant-factor approximation, assuming Feige's Random k-AND assumption.

Joint work with Julia Chuzhoy, Yury Makarychev and Aravindan Vijayaraghavan.

ABSTRACT:

We study the k-route cut problem: given an undirected edge-weighted graph G=(V,E), a collection {(s_1,t_1),(s_2,t_2),...,(s_r,t_r)} of source-sink pairs, and an integer connectivity requirement k, the goal is to find a minimum-weight subset E' of edges to remove, such that the connectivity of each pair (s_i, t_i) falls below k. Specifically, in the edge-connectivity version, EC-kRC, the requirement is that there are at most (k-1) edge-disjoint paths connecting s_i to t_i in G \ E', while in the vertex-connectivity version, VC-kRC, the same requirement is for vertex-disjoint paths. Prior to our work, poly-logarithmic approximation algorithm has been known for the special case where k=2, but no non-trivial approximation algorithms were known for any value k > 2, except in the single-source setting. We show an O(k log^{3/2}r)-approximation algorithm for EC-kRC with uniform edge weights, and several polylogarithmic bi-criteria approximation algorithms for EC-kRC and VC-kRC, where the connectivity requirement k is violated by a constant factor. Our results improve the previously known result for the case k=2. We also prove that VC-kRC is hard to approximate up to a factor of k^{\epsilon} for some fixed \epsilon > 0.

We then turn to study a simpler version of VC-kRC, where only one source-sink pair is present. We present a simple bi-criteria approximation algorithm for this case. Then we show evidence that even this restricted version of the problem may be hard to approximate. For example, we show that the single source-sink pair version of VC-kRC has no constant-factor approximation, assuming Feige's Random k-AND assumption.

Joint work with Julia Chuzhoy, Yury Makarychev and Aravindan Vijayaraghavan.