LIPIcs.APPROX-RANDOM.2022.55.pdf
- Filesize: 2.63 MB
- 18 pages
Document
A Primal-Dual Algorithm for Multicommodity Flows and Multicuts in Treewidth-2 Graphs
Authors
Tobias Friedrich 
,
Davis Issac ,
Nikhil Kumar ,
Nadym Mallek ,
Ziena Zeif
-
Part of:
Volume:
Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2022)
Series: Leibniz International Proceedings in Informatics (LIPIcs)
Conference: International Conference on Randomization and Computation (RANDOM)
Conference: International Conference on Approximation Algorithms for Combinatorial Optimization Problems (APPROX) - License:
Creative Commons Attribution 4.0 International license
- Publication Date: 2022-09-15
File
Document Identifiers
Author Details
Cite AsGet BibTex
Tobias Friedrich, Davis Issac, Nikhil Kumar, Nadym Mallek, and Ziena Zeif. A Primal-Dual Algorithm for Multicommodity Flows and Multicuts in Treewidth-2 Graphs. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 245, pp. 55:1-55:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
https://doi.org/10.4230/LIPIcs.APPROX/RANDOM.2022.55
https://doi.org/10.4230/LIPIcs.APPROX/RANDOM.2022.55
Abstract
We study the problem of multicommodity flow and multicut in treewidth-2 graphs and prove bounds on the multiflow-multicut gap. In particular, we give a primal-dual algorithm for computing multicommodity flow and multicut in treewidth-2 graphs and prove the following approximate max-flow min-cut theorem: given a treewidth-2 graph, there exists a multicommodity flow of value f with congestion 4, and a multicut of capacity c such that c ≤ 20 f. This implies a multiflow-multicut gap of 80 and improves upon the previous best known bounds for such graphs. Our algorithm runs in polynomial time when all the edges have capacity one. Our algorithm is completely combinatorial and builds upon the primal-dual algorithm of Garg, Vazirani and Yannakakis for multicut in trees and the augmenting paths framework of Ford and Fulkerson.
Subject Classification
ACM Subject Classification
- Theory of computation → Graph algorithms analysis
Keywords
- Approximation Algorithms
- Multicommodity Flow
- Multicut
Metrics
- Access Statistics
-
Total Accesses (updated on a weekly basis)
0PDF Downloads
References
-
Ittai Abraham, Cyril Gavoille, Anupam Gupta, Ofer Neiman, and Kunal Talwar. Cops, robbers, and threatening skeletons: Padded decomposition for minor-free graphs. In Proceedings of the forty-sixth annual ACM symposium on Theory of computing, pages 79-88, 2014.
-
Chandra Chekuri, Sanjeev Khanna, and F Bruce Shepherd. An O(√n) approximation and integrality gap for disjoint paths and unsplittable flow. Theory of computing, 2(1):137-146, 2006.
-
Chandra Chekuri, Guyslain Naves, and F Bruce Shepherd. Maximum edge-disjoint paths in k-sums of graphs. In International Colloquium on Automata, Languages, and Programming, pages 328-339. Springer, 2013.
-
Julia Chuzhoy and Shi Li. A polylogarithmic approximation algorithm for edge-disjoint paths with congestion 2. In 2012 IEEE 53rd Annual Symposium on Foundations of Computer Science, pages 233-242. IEEE, 2012.
- Denis Cornaz. Max-multiflow/min-multicut for G+H series-parallel. Discret. Math., 311(17):1957-1967, 2011. URL: https://doi.org/10.1016/j.disc.2011.05.025.
- Alina Ene, Matthias Mnich, Marcin Pilipczuk, and Andrej Risteski. On routing disjoint paths in bounded treewidth graphs. arXiv preprint, 2015. URL: http://arxiv.org/abs/1512.01829.
-
Lester Randolph Ford and Delbert R Fulkerson. Maximal flow through a network. In Classic papers in combinatorics, pages 243-248. Springer, 2009.
-
Naveen Garg and Nikhil Kumar. Dual half-integrality for uncrossable cut cover and its application to maximum half-integral flow. In 28th Annual European Symposium on Algorithms (ESA 2020), volume 173, page 55. Schloss Dagstuhl - Leibniz-Zentrum for Informatik, 2020.
-
Naveen Garg, Nikhil Kumar, and András Sebö. Integer plane multiflow maximisation: Flow-cut gap and one-quarter-approximation. In International Conference on Integer Programming and Combinatorial Optimization, pages 144-157. Springer, 2020.
-
Naveen Garg, Vijay V Vazirani, and Mihalis Yannakakis. Approximate max-flow min-(multi) cut theorems and their applications. SIAM Journal on Computing, 25(2):235-251, 1996.
-
Naveen Garg, Vijay V. Vazirani, and Mihalis Yannakakis. Primal-dual approximation algorithms for integral flow and multicut in trees. Algorithmica, 18(1):3-20, 1997.
-
T Chiang Hu. Multi-commodity network flows. Operations research, 11(3):344-360, 1963.
-
Philip Klein, Serge A Plotkin, and Satish Rao. Excluded minors, network decomposition, and multicommodity flow. In Proceedings of the twenty-fifth annual ACM symposium on Theory of computing, pages 682-690. ACM, 1993.
-
Takao Nishizeki, Jens Vygen, and Xiao Zhou. The edge-disjoint paths problem is np-complete for series-parallel graphs. Discrete Applied Mathematics, 115(1-3):177-186, 2001.
-
Loïc Seguin-Charbonneau and F Bruce Shepherd. Maximum edge-disjoint paths in planar graphs with congestion 2. In IEEE 52nd Annual Symposium on Foundations of Computer Science (FOCS), pages 200-209. IEEE, 2011.
-
Eva Tardos and Vijay V Vazirani. Improved bounds for the max-flow min-multicut ratio for planar and kr, r-free graphs. Information Processing Letters, 47(2):77-80, 1993.
-
Hui Zang, Jason P Jue, and Biswanath Mukherjee. A review of routing and wavelength assignment approaches for wavelength-routed optical wdm networks. Optical networks magazine, 1(1):47-60, 2000.