research-article

When the cut condition is enough: a complete characterization for multiflow problems in series-parallel networks

Authors:

Amit Chakrabarti,

Lisa Fleischer,

Christophe WeibelAuthors Info & Claims

STOC '12: Proceedings of the forty-fourth annual ACM symposium on Theory of computing

Pages 19 - 26

https://doi.org/10.1145/2213977.2213980

Published: 19 May 2012 Publication History

Abstract

Let G=(V,E) be a supply graph and H=(V,F) a demand graph defined on the same set of vertices. An assignment of capacities to the edges of G and demands to the edges of H is said to satisfy the cut condition if for any cut in the graph, the total demand crossing the cut is no more than the total capacity crossing it. The pair (G,H) is called cut-sufficient if for any assignment of capacities and demands that satisfy the cut condition, there is a multiflow routing the demands defined on $H$ within the network with capacities defined on G.

We prove a previous conjecture, which states that when the supply graph G is series-parallel, the pair (G,H) is cut-sufficient if and only if (G,H) does not contain an odd spindle as a minor; that is, if it is impossible to contract edges of G and delete edges of G and H so that G becomes the complete bipartite graph K_2,p, with p ≥ 3 odd, and H is composed of a cycle connecting the p vertices of degree 2, and an edge connecting the two vertices of degree p. We further prove that if the instance is Eulerian --- that is, the demands and capacities are integers and the total of demands and capacities incident to each vertex is even --- then the multiflow problem has an integral solution. We provide a polynomial-time algorithm to find an integral solution in this case.

In order to prove these results, we formulate properties of tight cuts (cuts for which the cut condition inequality is tight) in cut-sufficient pairs. We believe these properties might be useful in extending our results to planar graphs.

Supplementary Material

JPG File (stoc_1a_2.jpg)

Download
11.69 KB

MP4 File (stoc_1a_2.mp4)

Download
137.06 MB

References

[1]

Y. Aumann and Y. Rabani. An O(log k) approximate min-cut max-flow theorem and approximation algorithm. SIAM J. Comput, 27:291--301, 1998.

Digital Library

[2]

A. Chakrabarti, A. Jaffe, J. Lee, and J. Vincent. Embeddings of topological graphs: Lossy invariants, linearization, and 2-sums. In Foundations of Computer Science, 2008. FOCS '08. IEEE 49th Annual IEEE Symposium on, pages 761 --770, October 2008.

Digital Library

[3]

C. Chekuri, B. Shepherd, and C. Weibel. Flow-cut gaps for integer and fractional multiflows. Submitted to the Journal of Computational Theory Series B; available at arXiv:1008.2136v1, July 2010.

Digital Library

[4]

C. Chekuri, B. Shepherd, and C. Weibel. Flow-cut gaps for integer and fractional multiflows. In Proceedings of the 21st Annual ACM-SIAM Symposium on Discrete Algorithm (SoDA 2010), pages 1198--1208, January 2010.

Digital Library

[5]

O. Günlük. A new min-cut max-flow ratio for multicommodity flows. SIAM J. Discret. Math., 21(1):1--15, 2007.

Digital Library

[6]

A. Gupta, I. Newman, Y. Rabinovich, and A. Sinclair. Cuts, trees and l1-embeddings of graphs. Combinatorica, 24(2):233--269, 2004.

Digital Library

[7]

T. C. Hu. Multi-commodity network flows. Operations Research, 11(3):344--360, 1963.

Digital Library

[8]

J. R. Lee and P. Raghavendra. Coarse differentiation and multi-flows in planar graphs. In APPROX '07/RANDOM '07: Proceedings of the 10th International Workshop on Approximation and the 11th International Workshop on Randomization, and Combinatorial Optimization. Algorithms and Techniques, pages 228--241, Berlin, Heidelberg, 2007. Springer-Verlag.

Digital Library

[9]

T. Leighton and S. Rao. Multicommodity max-flow min-cut theorems and their use in designing approximation algorithms. J. ACM, 46(6):787--832, 1999.

Digital Library

[10]

N. Linial, E. London, and Y. Rabinovich. The geometry of graphs and some of its algorithmic applications. Combinatorica, 15:577--591, 1994.

[11]

Lomonosov. Combinatorial approaches to multiflow problems. Discrete Applied Mathematics, 11(1):1 -- 93, 1985.

[12]

T. Nishizeki, J. Vygen, and X. Zhou. The edge-disjoint paths problem is NP-complete for series-parallel graphs. Discrete Applied Mathematics, 115(1--3):177--186, 2001.

Digital Library

[13]

H. Okamura. Multicommodity flows in graphs. Discrete Applied Mathematics, 6(1):55 -- 62, 1983.

[14]

H. Okamura and P. Seymour. Multicommodity flows in planar graphs. Journal of Combinatorial Theory, Series B, 31(1):75 -- 81, 1981.

[15]

W. Schnyder. Embedding planar graphs on the grid. In Proceedings of the first annual ACM-SIAM symposium on Discrete algorithms (SoDA 1990), SODA '90, pages 138--148, Philadelphia, PA, USA, 1990. Society for Industrial and Applied Mathematics.

Digital Library

[16]

A. Schrijver. The Klein bottle and multicommodity flows. Combinatorica, 9:375--384, 1989. 10.1007/BF02125349.

[17]

A. Schrijver. Combinatorial Optimization: Polyhedra and Efficieny, volume 24 of Algorithms and Combinatorics. Springer-Verlag, New York, 2003.

[18]

P. Seymour. Matroids and multicommodity flows. European Journal of Combinatorics, 2:257--290, 1981.

[19]

P. Seymour. On odd cuts and plane multicommodity flows. Proceedings of the London Mathematical Society, 3(1):178, 1981.

Cited By

Naves GShepherd B(2022)When Do Gomory--Hu Subtrees Exist?SIAM Journal on Discrete Mathematics10.1137/20M135696836:3(1567-1585)Online publication date: 1-Jan-2022
https://dl.acm.org/doi/10.1137/20M1356968
Kumar N(2022)An Approximate Generalization of the Okamura-Seymour Theorem2022 IEEE 63rd Annual Symposium on Foundations of Computer Science (FOCS)10.1109/FOCS54457.2022.00106(1093-1101)Online publication date: Oct-2022
https://doi.org/10.1109/FOCS54457.2022.00106
Cohen-Addad VGupta AKlein PLi JKhuller SVassilevska Williams V(2021)A quasipolynomial (2 + ε)-approximation for planar sparsest cutProceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing10.1145/3406325.3451103(1056-1069)Online publication date: 15-Jun-2021
https://dl.acm.org/doi/10.1145/3406325.3451103
Show More Cited By

Index Terms

When the cut condition is enough: a complete characterization for multiflow problems in series-parallel networks
1. Theory of computation
  1. Randomness, geometry and discrete structures

Recommendations

The circular chromatic number of series-parallel graphs

In this article, we consider the circular chromatic number χ_c(G) of series-parallel graphs G. It is well known that series-parallel graphs have chromatic number at most 3. Hence, their circular chromatic numbers are at most 3. If a series-parallel graph ...
Small Drawings of Outerplanar Graphs, Series-Parallel Graphs, and Other Planar Graphs

In this paper, we study small planar drawings of planar graphs. For arbitrary planar graphs, ź(n2) is the established upper and lower bound on the worst-case area. A long-standing open problem is to determine for what graphs a smaller area can be ...
On graphs with no induced subdivision of K4

We prove a decomposition theorem for graphs that do not contain a subdivision of K"4 as an induced subgraph where K"4 is the complete graph on four vertices. We obtain also a structure theorem for the class C of graphs that contain neither a subdivision ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

STOC '12: Proceedings of the forty-fourth annual ACM symposium on Theory of computing

May 2012

1310 pages

ISBN:9781450312455

DOI:10.1145/2213977

General Chair:
Howard Karloff
AT&T Labs--Research
,
Program Chair:
Toniann Pitassi
University of Toronto

Copyright © 2012 ACM.

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]

Sponsors

SIGACT: ACM Special Interest Group on Algorithms and Computation Theory

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 19 May 2012

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Conference

STOC'12

Sponsor:

SIGACT

STOC'12: Symposium on Theory of Computing

May 19 - 22, 2012

New York, New York, USA

Acceptance Rates

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

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

10
Total Citations
View Citations
36
Total Downloads

Downloads (Last 12 months)7
Downloads (Last 6 weeks)0

Reflects downloads up to 14 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Naves GShepherd B(2022)When Do Gomory--Hu Subtrees Exist?SIAM Journal on Discrete Mathematics10.1137/20M135696836:3(1567-1585)Online publication date: 1-Jan-2022
https://dl.acm.org/doi/10.1137/20M1356968
Kumar N(2022)An Approximate Generalization of the Okamura-Seymour Theorem2022 IEEE 63rd Annual Symposium on Foundations of Computer Science (FOCS)10.1109/FOCS54457.2022.00106(1093-1101)Online publication date: Oct-2022
https://doi.org/10.1109/FOCS54457.2022.00106
Cohen-Addad VGupta AKlein PLi JKhuller SVassilevska Williams V(2021)A quasipolynomial (2 + ε)-approximation for planar sparsest cutProceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing10.1145/3406325.3451103(1056-1069)Online publication date: 15-Jun-2021
https://dl.acm.org/doi/10.1145/3406325.3451103
Bäuml SAzuma KKato GElkouss D(2020)Linear programs for entanglement and key distribution in the quantum internetCommunications Physics10.1038/s42005-020-0318-23:1Online publication date: 20-Mar-2020
https://doi.org/10.1038/s42005-020-0318-2
Yin XLi ZLiu YWang X(2018)A Reduction Approach to the Multiple-Unicast Conjecture in Network CodingIEEE Transactions on Information Theory10.1109/TIT.2017.277173864:6(4530-4539)Online publication date: Jun-2018
https://doi.org/10.1109/TIT.2017.2771738
Grappe RLacroix M(2018) The st -bond polytope on series-parallel graphs RAIRO - Operations Research10.1051/ro/201803552:3(923-934)Online publication date: 22-Oct-2018
https://doi.org/10.1051/ro/2018035
Bartolini NCiavarella SLa Porta TSilvestri S(2017)On Critical Service Recovery After Massive Network FailuresIEEE/ACM Transactions on Networking10.1109/TNET.2017.268833025:4(2235-2249)Online publication date: 1-Aug-2017
https://dl.acm.org/doi/10.1109/TNET.2017.2688330
Yin XLi ZWang X(2016)A reduction approach to the multiple-unicast conjecture in network coding2016 IEEE International Symposium on Information Theory (ISIT)10.1109/ISIT.2016.7541604(1774-1778)Online publication date: Jul-2016
https://doi.org/10.1109/ISIT.2016.7541604
Bartolini NCiavarella SPorta TSilvestri S(2016)Network Recovery After Massive Failures2016 46th Annual IEEE/IFIP International Conference on Dependable Systems and Networks (DSN)10.1109/DSN.2016.18(97-108)Online publication date: Jun-2016
https://doi.org/10.1109/DSN.2016.18
Chekuri CShepherd FWeibel C(2013)Flow-cut gaps for integer and fractional multiflowsJournal of Combinatorial Theory Series B10.1016/j.jctb.2012.11.002103:2(248-273)Online publication date: 1-Mar-2013
https://dl.acm.org/doi/10.1016/j.jctb.2012.11.002

View Options

Get Access

Login options

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

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Table of Contents