  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 every 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, NC-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 log^{3/2}r)-approximation algorithm
for EC-kRC with uniform edge weights, and several polylogarithmic bi-criteria
approximation algorithms for EC-kRC and NC-kRC, where the connectivity
requirement k is violated by a constant factor. We complement these upper
bounds by proving that NC-kRC is hard to approximate to within a factor of
k^{eps} for some fixed eps>0.
  We then turn to study a simpler version of NC-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 NC-kRC has no constant-factor approximation, assuming Feige's Random
k-AND assumption.
