Approximation algorithms and hardness of the k-route cut problem
Julia Chuzhoy, Yury Makarychev, Aravindan Vijayaraghavan, Yuan Zhou · 2012
We study the k-route cut problem: given an undirected edge-weighted graph G = (V,E), a collection {(s1, t1), (s2, t2),..., (sr, tr)} of source-sink pairs, and an integer connectivity re-quirement k, the goal is to find a minimum-weight subset E ′ of edges to remove, such that the connectivity of every pair (si, ti) 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 si to ti 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 algorithms have been known for the special case where k ≤ 3, but no non-trivial approximation algorithms were known for any value k> 3, except in the single-source setting. We show an O(k log3/2 r)-approximation algorithm for EC-kRC with uniform edge weights, and several polylogarithmic bi-criteria approx-imation algorithms for EC-kRC and VC-kRC, where the connectivity requirement k is violated by a constant factor. We complement these upper bounds by proving that VC-kRC is hard to approximate to within a factor of k for some fixed > 0. We then turn to study a simpler version of VC-kRC, where only one source-sink pair is present. We give a simple bi-criteria approximation algorithm for this case, and show evidence that even this restricted version of the problem may be hard to approximate. For example, we prove that the single source-sink pair version of VC-kRC has no constant-factor approximation, assuming Feige’s Random κ-AND assumption. 1