Article

Approximate max-integral-flow/min-multicut theorems

Author:

Kenji ObataAuthors Info & Claims

STOC '04: Proceedings of the thirty-sixth annual ACM symposium on Theory of computing

Pages 539 - 545

https://doi.org/10.1145/1007352.1007433

Published: 13 June 2004 Publication History

Get Access

Abstract

We establish several approximate max-integral-flow / min-multicut theorems. While in general this ratio can be very large, we prove strong approximation ratios in the case where the min-multicut is a constant fraction ε of the total capacity of the graph. This setting is motivated by several combinatorial and algorithmic applications. Prior to this work, a general max-integral-flow / min-multicut bound was known only for the special case where the graph is a tree. We prove that, for arbitrary graphs, the max-integral-flow / min-multicut ratio is O(ε^-1 log k), where k is the number of commodites; for graphs excluding a fixed subgraph as a minor (for instance, planar graphs), O(1 / ε); and, for dense graphs, O(1√ε). Our proofs are constructive in the sense that we give efficient algorithms which compute either an integral flow achieving the claimed approximation ratios, or a witness that the precondition is violated.

References

[1]

Y. Aumann and Y. Rabani. An O (log k) approximate min-cut max-flow theorem and approximation algorithm. SIAM Journal on Computing, 27(1):291--301, 1998.]]

Digital Library

Google Scholar

[2]

A. Bogdanov, K. Obata, and L. Trevisan. A lower bound for testing 3-colorability. In IEEE Symposium on Foundations of Computer Science, pages 93--102, 2002.]]

Digital Library

Google Scholar

[3]

B. Bollobás, P. Erdös, M. Simonovits, and E. Szemerédi. Extremal graphs without large forbidden subgraphs. Annals of Discrete Mathematics, 3:29--41, 1978.]]

Crossref

Google Scholar

[4]

C. Chekuri and S. Khanna. Edge disjoint paths revisited. In ACM-SIAM Symposium on Discrete Algorithms, pages 628--637, 2003.]]

Digital Library

Google Scholar

[5]

E. Dahlhaus, D. Johnson, C. Papadimitriou, P. Seymour, and M. Yannakakis. The complexity of multiterminal cuts. SIAM Journal on Computing, 23:864--894, 1994.]]

Digital Library

Google Scholar

[6]

L. Ford and D. R. Fulkerson. Maximal flow through a network. Canadian Journal of Mathematics, 8, 1956.]]

Google Scholar

[7]

N. Garg, V. V. Vazirani, and M. Yannakakis. Approximate max-flow min-(multi)cut theorems and their applications. In ACM Symposium on Theory of Computing, pages 698--707, 1993.]]

Digital Library

Google Scholar

[8]

N. Garg, V. V. Vazirani, and M. Yannakakis. Primal-dual approximation algorithms for integral flow and multicut in trees. Algorithmica, 18:3--20, 1997.]]

Digital Library

Google Scholar

[9]

O. Goldreich, S. Goldwasser, and D. Ron. Property testing and its connection to learning and approximation. Journal of the ACM, 45(4):653--750, 1998.]]

Digital Library

Google Scholar

[10]

O. Goldreich and D. Ron. Property testing in bounded degree graphs. In ACM Symposium on Theory of Computing, pages 406--415, 1997.]]

Digital Library

Google Scholar

[11]

O. Günlük. A new min-cut max-flow ratio for multicommodity flows. In Integer Programming and Combinatorial Optimization, pages 54--66, 2002.]]

Digital Library

Google Scholar

[12]

R. M. Karp. Reducibility among combinatorial problems. In R. E. Miller and J. W. Thatcher, editors, Complexity of Computer Computations, pages 85--103, New York, NY, 1972. Plenum Press.]]

Crossref

Google Scholar

[13]

P. Klein, S. Plotkin, and S. Rao. Excluded minors, network decomposition, and multicommodity flow. In ACM Symposium on Theory of Computing, pages 682--690, 1993.]]

Digital Library

Google Scholar

[14]

J. Kleinberg. Approximation algorithms for disjoint paths problems. Ph. D. Thesis, MIT, Cambridge, MA, 1996.]]

Digital Library

Google Scholar

[15]

S. G. Kolliopoulos and C. Stein. Approximating disjoint-path problems using greedy algorithms and packing integer programs. In Integer Programming and Combinatorial Optimization, 1998.]]

Crossref

Google Scholar

[16]

J. Komlós. Covering odd cycles. Combinatorica, pages 393--400, 1997.]]

Google Scholar

[17]

F. T. Leighton and S. Rao. An approximate max-flow min-cut theorem for uniform multi-commodity flow problems with applications to approximation algorithms. Journal of the ACM, 46(6), 1999.]]

Digital Library

Google Scholar

[18]

N. Linial, E. London, and Y. Rabinovich. The geometry of graphs and some of its algorithmic applications. Combinatorica, 15:215--245, 1995.]]

Crossref

Google Scholar

[19]

S. Plotkin and E. Tardos. Improved bounds on the max-flow min-cut ratio for multicommodity flows. In ACM Symposium on Theory of Computing, pages 691--697, 1993.]]

Digital Library

Google Scholar

[20]

K. Varadarajan and G. Venkataraman. Graph decomposition and a greedy algorithm for edge-disjoint paths. In ACM-SIAM Symposium on Discrete Algorithms, 2004.]]

Digital Library

Google Scholar

Cited By

View all

Iwama KYoshida Y(2017)Parameterized TestabilityACM Transactions on Computation Theory10.1145/31552949:4(1-16)Online publication date: 14-Dec-2017
https://dl.acm.org/doi/10.1145/3155294
Iwama KYoshida YNaor M(2014)Parameterized testabilityProceedings of the 5th conference on Innovations in theoretical computer science10.1145/2554797.2554843(507-516)Online publication date: 12-Jan-2014
https://dl.acm.org/doi/10.1145/2554797.2554843
Bentz C(2009)Disjoint paths in sparse graphsDiscrete Applied Mathematics10.1016/j.dam.2009.03.009157:17(3558-3568)Online publication date: 1-Oct-2009
https://dl.acm.org/doi/10.1016/j.dam.2009.03.009
Show More Cited By

Index Terms

Approximate max-integral-flow/min-multicut theorems
1. Mathematics of computing
  1. Discrete mathematics
    1. Graph theory
      1. Paths and connectivity problems
  2. Mathematical analysis
    1. Mathematical optimization
      1. Continuous optimization
        Linear programming
2. Theory of computation
  1. Design and analysis of algorithms
    1. Mathematical optimization
      1. Continuous optimization
        Linear programming
  2. Randomness, geometry and discrete structures

Recommendations

Parameterized complexity dichotomy for Steiner Multicut

We consider the Steiner Multicut problem, which asks, given an undirected graph G, a collection T = { T 1 , ź , T t } , T i ź V ( G ) , of terminal sets of size at most p, and an integer k, whether there is a set S of at most k edges or nodes such that ...
Approximate Max-Flow Min-Multicut Theorem for Graphs of Bounded Treewidth
STOC 2023: Proceedings of the 55th Annual ACM Symposium on Theory of Computing

We prove an approximate max-multiflow min-multicut theorem for bounded treewidth graphs. In particular, we show the following: Given a treewidth-r graph, there exists a (fractional) multicommodity flow of value f, and a multicut of capacity c such ...
The complexity of multicut and mixed multicut problems in (di)graphs

The multicut problem with respect to the fixed pattern (di)graph Q is the following: given a (di)graph G, an integer k and a 1-1 mapping @p of the vertices of Q to a subset X of V(G); determine whether there exists a set S of at most k edges (arcs) of G ...

Reviews

Reviewer: Chenyi Hu

Studying the maximum capacity between two vertices of a network has many practical applications. According to Ford and Fulkerson, the max-flow and min cut theorem is: the value of a maximum flow between two vertices is equal to the capacity of a minimum cut in a weighted graph (network). Algorithms to find the paths of the maximum flow have also been developed. The study of the maximum flow and minimum cut of a weighted graph has been active in both theoretical and application-oriented work. In this paper, the author reports on his most recent theoretical results, of bounding the approximated ratio of max-integral-flow and minimum multicuts of multicommodity flow with low-radius decompositions. The main results are: (1) The ratio of max-integral-flow and minimum multicuts, for arbitrary graphs, is O(&egr; -1log k ), where k is the number of commodities, and &egr; represents a constant fraction of the total capacity of the graph. (2) The ratio is O(1/&egr;) for graphs excluding a fixed subgraph as a minor. (3) The ratio is O(1/v&egr;) if the graph is dense. The constructive proof provides approximation algorithms that may also be used in combinatorial applications. This theoretic paper is very well written. Online Computing Reviews Service

Access critical reviews of Computing literature here

Become a reviewer for Computing Reviews.

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

STOC '04: Proceedings of the thirty-sixth annual ACM symposium on Theory of computing

June 2004

660 pages

ISBN:1581138520

DOI:10.1145/1007352

Program Chair:
László Babai
University of Chicago, Chicago, IL

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 13 June 2004

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Qualifiers

Article

Conference

STOC04

Sponsor:

STOC04: Symposium of Theory of Computing 2004

June 13 - 16, 2004

IL, Chicago, USA

Acceptance Rates

Overall Acceptance Rate 1,469 of 4,586 submissions, 32%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

6
Total Citations
View Citations
558
Total Downloads

Downloads (Last 12 months)4
Downloads (Last 6 weeks)1

Reflects downloads up to 28 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

View all

Iwama KYoshida Y(2017)Parameterized TestabilityACM Transactions on Computation Theory10.1145/31552949:4(1-16)Online publication date: 14-Dec-2017
https://dl.acm.org/doi/10.1145/3155294
Iwama KYoshida YNaor M(2014)Parameterized testabilityProceedings of the 5th conference on Innovations in theoretical computer science10.1145/2554797.2554843(507-516)Online publication date: 12-Jan-2014
https://dl.acm.org/doi/10.1145/2554797.2554843
Bentz C(2009)Disjoint paths in sparse graphsDiscrete Applied Mathematics10.1016/j.dam.2009.03.009157:17(3558-3568)Online publication date: 1-Oct-2009
https://dl.acm.org/doi/10.1016/j.dam.2009.03.009
Rao SZhou S(2006)Edge disjoint paths in moderately connected graphsProceedings of the 33rd international conference on Automata, Languages and Programming - Volume Part I10.1007/11786986_19(202-213)Online publication date: 10-Jul-2006
https://dl.acm.org/doi/10.1007/11786986_19
Bentz C(2005)Edge disjoint paths and max integral multiflow/min multicut theorems in planar graphsElectronic Notes in Discrete Mathematics10.1016/j.endm.2005.06.01022(55-60)Online publication date: Oct-2005
https://doi.org/10.1016/j.endm.2005.06.010
Commission P(undefined)Financial Performance of Government Trading Enterprises 1999-00 to 2003-04SSRN Electronic Journal10.2139/ssrn.883470
https://doi.org/10.2139/ssrn.883470

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Cited By

Index Terms

Recommendations

Parameterized complexity dichotomy for Steiner Multicut

Approximate Max-Flow Min-Multicut Theorem for Graphs of Bounded Treewidth

The complexity of multicut and mixed multicut problems in (di)graphs

Reviews

Access critical reviews of Computing literature here