skip to main content
10.5555/1109557.1109625acmconferencesArticle/Chapter ViewAbstractPublication PagessodaConference Proceedingsconference-collections
Article

Approximating the k-multicut problem

Published: 22 January 2006 Publication History

Abstract

We study the k-multicut problem: Given an edge-weighted undirected graph, a set of l pairs of vertices, and a target kl, find the minimum cost set of edges whose removal disconnects at least k pairs. This generalizes the well known multicut problem, where k = l. We show that the k-multicut problem on trees can be approximated within a factor of 8/3 + ε, for any fixed ε > 0, and within O(log2 n log log n) on general graphs, where n is the number of vertices in the graph.For any fixed ε > 0, we also obtain a polynomial time algorithm for k-multicut on trees which returns a solution of cost at most (2 + ε) · OPT, that separates at least (1 - ε) · k pairs, where OPT is the cost of the optimal solution separating k pairs.Our techniques also give a simple 2-approximation algorithm for the multicut problem on trees using total unimodularity, matching the best known algorithm [8].

References

[1]
Noga Alon, Baruch Awerbuch, Yossi Azar, Niv Buchbinder, and Joseph (Seffi) Naor. A general approach to online network optimization problems. Proc. ACM-SIAM symposium on Discrete algorithms, pages 577--586, 2004.
[2]
Chandra Chekuri, Marcelo Mydlarz, and F. Bruce Shepherd. Multicommodity demand flow in a tree. In Proc. International Colloquium on Automata, Languages and Programming, pages 410--425, 2003.
[3]
Lester R. Ford and Delbert R. Fulkerson. Maximal flow through a network. Canadian Journal of Mathematics, 8:399--404, 1956.
[4]
Greg N. Frederickson and Joseph JáJá. Approximation algorithm for several graph augmentation problems. SIAM J. Comput., 10(2):270--283, 1981.
[5]
Rajiv Gandhi, Samir Khuller, and Aravind Srinivasan. Approximation algorithms for partial covering problems. J. Algorithms, 53(1):55--84, 2004.
[6]
Naveen Garg. Saving an epsilon: a 2-approximation for the k-MST problem in graphs. Proc. ACM Symposium on Theory of Computing, pages 396--402, 2005.
[7]
Naveen Garg, Vijay V. Vazirani, and Mihalis Yannakakis. Approximate max-flow min-(multi)cut theorems and their applications. Proc. ACM Symposium on Theory of Computing, pages 698--707, 1993.
[8]
Naveen Garg, Vijay V. Vazirani, and Mihalis Yannakakis. Primal-dual approximation algorithms for integral flow and multicut in trees. Algorithmica, 18:3--20, 1997.
[9]
Chris Harrelson, Kirsten Hildrum, and Satish Rao. A polynomial-time tree decomposition to minimize congestion. Proc. ACM Symposium on Parallel Algorithms and Architectures, pages 34--43, 2003.
[10]
Refael Hassin and Danny Segev. Rounding to an integral program. Proc. International Workshop on Efficient and Experimental Algorithms, pages 44--54, 2005.
[11]
Dorit S. Hochbaum. Instant recognition of half integrality and 2-approximations. Proc. International Workshop on Approximation Algorithms for Combinatorial Optimization, pages 99--110, 1998.
[12]
Kamal Jain and Vijay V. Vazirani. Primal-dual approximation algorithms for metric facility location and k-median problems. Proc. IEEE Symposium on Foundations of Computer Science, page 2, 1999.
[13]
Stavros G. Kolliopoulos and Clifford Stein. Approximation algorithms for single-source unsplittable flow. SIAM J. Comput., 31(3):919--946, 2001.
[14]
Jochen Könemann and R. Ravi. A matter of degree: improved approximation algorithms for degree-bounded minimum spanning trees. Proc. ACM symposium on Theory of computing, pages 537--546, 2000.
[15]
Tom Leighton and Satish Rao. Multicommodity max-flow min-cut theorems and their use in designing approximation algorithms. J. ACM, 46(6):787--832, 1999.
[16]
George L. Nemhauser and Laurence A. Wolsey. Integer and Combinatorial Optimization. 1999.
[17]
Harald Räcke. Minimizing congestion in general networks. Proc. IEEE Symposium on Foundations of Computer Science, pages 43--52, 2002.
[18]
R. Ravi. 2-approximation for augmentating a tree to be 2-edge connected using total unimodularity. Personal Communication. 2004.
[19]
R. Ravi and Michel X. Goemans. The constrained minimum spanning tree problem. Proc. Scandinavian Workshop on Algorithm Theory, pages 66--75, 1996.
[20]
Danny Segev. Personal Communication. 2005.
[21]
Danny Segev and Asaf Levin. Partial multicuts in trees. To appear, Workshop on Approximation and Online Algorithms, 2005.
[22]
David B. Shmoys. Cut problems and their application to divide-and-conquer. Approximation Algorithms for NP-hard Problems, pages 192--235, 1997.

Cited By

View all

Recommendations

Comments

Information & Contributors

Information

Published In

cover image ACM Conferences
SODA '06: Proceedings of the seventeenth annual ACM-SIAM symposium on Discrete algorithm
January 2006
1261 pages
ISBN:0898716055

Sponsors

Publisher

Society for Industrial and Applied Mathematics

United States

Publication History

Published: 22 January 2006

Check for updates

Qualifiers

  • Article

Acceptance Rates

Overall Acceptance Rate 411 of 1,322 submissions, 31%

Contributors

Other Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

  • Downloads (Last 12 months)3
  • Downloads (Last 6 weeks)0
Reflects downloads up to 17 Feb 2025

Other Metrics

Citations

Cited By

View all
  • (2019)An FPT Algorithm for Planar Multicuts with Sources and Sinks on the Outer FaceAlgorithmica10.1007/s00453-018-0443-481:1(224-237)Online publication date: 1-Jan-2019
  • (2014)Thresholded covering algorithms for robust and max---min optimizationMathematical Programming: Series A and B10.5555/2650160.2650164146:1-2(583-615)Online publication date: 1-Aug-2014
  • (2014)Approximation algorithms for the partition vertex cover problemTheoretical Computer Science10.1016/j.tcs.2014.04.006555:C(2-8)Online publication date: 23-Oct-2014
  • (2012)An approximation algorithm for the Generalized k-Multicut problemDiscrete Applied Mathematics10.1016/j.dam.2012.01.016160:7-8(1240-1247)Online publication date: 1-May-2012
  • (2011)Resource allocation for covering time varying demandsProceedings of the 19th European conference on Algorithms10.5555/2040572.2040632(543-554)Online publication date: 5-Sep-2011
  • (2010)Thresholded covering algorithms for robust and max-min optimizationProceedings of the 37th international colloquium conference on Automata, languages and programming10.5555/1880918.1880948(262-274)Online publication date: 6-Jul-2010
  • (2009)On Profit-Maximizing Pricing for the Highway and Tollbooth ProblemsProceedings of the 2nd International Symposium on Algorithmic Game Theory10.1007/978-3-642-04645-2_25(275-286)Online publication date: 13-Oct-2009
  • (2009)Scheduling with OutliersProceedings of the 12th International Workshop and 13th International Workshop on Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques10.1007/978-3-642-03685-9_12(149-162)Online publication date: 21-Aug-2009
  • (2008)Approximation algorithms for k-hurdle problemsProceedings of the 8th Latin American conference on Theoretical informatics10.5555/1792918.1792957(449-460)Online publication date: 7-Apr-2008
  • (2008)Optimal hierarchical decompositions for congestion minimization in networksProceedings of the fortieth annual ACM symposium on Theory of computing10.1145/1374376.1374415(255-264)Online publication date: 17-May-2008
  • Show More Cited By

View Options

Login options

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Figures

Tables

Media

Share

Share

Share this Publication link

Share on social media