### 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 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, 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 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. 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.

Original language | English (US) |
---|---|

Title of host publication | Proceedings of the 23rd Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2012 |

Publisher | Association for Computing Machinery |

Pages | 780-799 |

Number of pages | 20 |

ISBN (Print) | 9781611972108 |

DOIs | |

State | Published - Apr 30 2012 |

Externally published | Yes |

Event | 23rd Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2012 - Kyoto, Japan Duration: Jan 17 2012 → Jan 19 2012 |

### Publication series

Name | Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms |
---|

### Other

Other | 23rd Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2012 |
---|---|

Country | Japan |

City | Kyoto |

Period | 1/17/12 → 1/19/12 |

### ASJC Scopus subject areas

- Software
- Mathematics(all)

## Fingerprint Dive into the research topics of 'Approximation algorithms and hardness of the k-route cut problem'. Together they form a unique fingerprint.

## Cite this

*Proceedings of the 23rd Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2012*(pp. 780-799). (Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms). Association for Computing Machinery. https://doi.org/10.1137/1.9781611973099.63