Approximation algorithms and hardness of the k-route cut problem

Julia Chuzhoy, Yury Makarychev, Aravindan Vijayaraghavan, Yuan Zhou

Research output: Chapter in Book/Report/Conference proceedingConference contribution

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 languageEnglish (US)
Title of host publicationProceedings of the 23rd Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2012
Pages780-799
Number of pages20
StatePublished - Apr 30 2012
Externally publishedYes
Event23rd Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2012 - Kyoto, Japan
Duration: Jan 17 2012Jan 19 2012

Publication series

NameProceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms

Other

Other23rd Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2012
CountryJapan
CityKyoto
Period1/17/121/19/12

Fingerprint

Approximation algorithms
Hardness
Approximation Algorithms
Connectivity
Bicriteria
Requirements
Edge-disjoint Paths
Vertex Connectivity
Edge-connectivity
Disjoint Paths
Weighted Graph
Logarithmic
Complement
Upper bound
Integer
Subset
Approximation
Vertex of a graph

ASJC Scopus subject areas

  • Software
  • Mathematics(all)

Cite this

Chuzhoy, J., Makarychev, Y., Vijayaraghavan, A., & Zhou, Y. (2012). Approximation algorithms and hardness of the k-route cut problem. In 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).

Approximation algorithms and hardness of the k-route cut problem. / Chuzhoy, Julia; Makarychev, Yury; Vijayaraghavan, Aravindan; Zhou, Yuan.

Proceedings of the 23rd Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2012. 2012. p. 780-799 (Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms).

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Chuzhoy, J, Makarychev, Y, Vijayaraghavan, A & Zhou, Y 2012, Approximation algorithms and hardness of the k-route cut problem. in Proceedings of the 23rd Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2012. Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 780-799, 23rd Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2012, Kyoto, Japan, 1/17/12.
Chuzhoy J, Makarychev Y, Vijayaraghavan A, Zhou Y. Approximation algorithms and hardness of the k-route cut problem. In Proceedings of the 23rd Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2012. 2012. p. 780-799. (Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms).
Chuzhoy, Julia ; Makarychev, Yury ; Vijayaraghavan, Aravindan ; Zhou, Yuan. / Approximation algorithms and hardness of the k-route cut problem. Proceedings of the 23rd Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2012. 2012. pp. 780-799 (Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms).
@inproceedings{a9bb735adeb34185b43e2082b89299f1,
title = "Approximation algorithms and hardness of the k-route cut problem",
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.",
author = "Julia Chuzhoy and Yury Makarychev and Aravindan Vijayaraghavan and Yuan Zhou",
year = "2012",
month = "4",
day = "30",
language = "English (US)",
isbn = "9781611972108",
series = "Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms",
pages = "780--799",
booktitle = "Proceedings of the 23rd Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2012",

}

TY - GEN

T1 - Approximation algorithms and hardness of the k-route cut problem

AU - Chuzhoy, Julia

AU - Makarychev, Yury

AU - Vijayaraghavan, Aravindan

AU - Zhou, Yuan

PY - 2012/4/30

Y1 - 2012/4/30

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=84860189048&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84860189048&partnerID=8YFLogxK

M3 - Conference contribution

AN - SCOPUS:84860189048

SN - 9781611972108

T3 - Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms

SP - 780

EP - 799

BT - Proceedings of the 23rd Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2012

ER -