Approximation algorithms and hardness of the k-route cut problem

Julia Chuzhoy, Yury Makarychev, Aravindan Vijayaraghavan, Yuan Zhou

Research output: Contribution to journalArticle

Abstract

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 requirement 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(klog3/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)
Article number2
JournalACM Transactions on Algorithms
Volume12
Issue number1
DOIs
StatePublished - Dec 1 2015
Externally publishedYes

Fingerprint

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

Keywords

  • Approximation algorithm
  • K-route cut problem

ASJC Scopus subject areas

  • Mathematics (miscellaneous)

Cite this

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

In: ACM Transactions on Algorithms, Vol. 12, No. 1, 2, 01.12.2015.

Research output: Contribution to journalArticle

Chuzhoy, Julia ; Makarychev, Yury ; Vijayaraghavan, Aravindan ; Zhou, Yuan. / Approximation algorithms and hardness of the k-route cut problem. In: ACM Transactions on Algorithms. 2015 ; Vol. 12, No. 1.
@article{f0b07e5cc4404a57aa55df3b9a19a1ad,
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 {(s1, t1), (s2, t2), ⋯, (sr, tr)} 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 (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(klog3/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.",
keywords = "Approximation algorithm, K-route cut problem",
author = "Julia Chuzhoy and Yury Makarychev and Aravindan Vijayaraghavan and Yuan Zhou",
year = "2015",
month = "12",
day = "1",
doi = "10.1145/2644814",
language = "English (US)",
volume = "12",
journal = "ACM Transactions on Algorithms",
issn = "1549-6325",
publisher = "Association for Computing Machinery (ACM)",
number = "1",

}

TY - JOUR

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

AU - Chuzhoy, Julia

AU - Makarychev, Yury

AU - Vijayaraghavan, Aravindan

AU - Zhou, Yuan

PY - 2015/12/1

Y1 - 2015/12/1

N2 - 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 requirement 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(klog3/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 {(s1, t1), (s2, t2), ⋯, (sr, tr)} 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 (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(klog3/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.

KW - Approximation algorithm

KW - K-route cut problem

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

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

U2 - 10.1145/2644814

DO - 10.1145/2644814

M3 - Article

AN - SCOPUS:84954200150

VL - 12

JO - ACM Transactions on Algorithms

JF - ACM Transactions on Algorithms

SN - 1549-6325

IS - 1

M1 - 2

ER -