Document Open Access Logo

A Primal-Dual Algorithm for Multicommodity Flows and Multicuts in Treewidth-2 Graphs

Authors Tobias Friedrich , Davis Issac , Nikhil Kumar , Nadym Mallek , Ziena Zeif

PDF
Thumbnail PDF

File

LIPIcs.APPROX-RANDOM.2022.55.pdf
  • Filesize: 2.63 MB
  • 18 pages

Document Identifiers

Author Details

Tobias Friedrich
  • Hasso Plattner Institute, Universität Potsdam, Germany
Davis Issac
  • Hasso Plattner Institute, Universität Potsdam, Germany
Nikhil Kumar
  • Hasso Plattner Institute, Universität Potsdam, Germany
Nadym Mallek
  • Hasso Plattner Institute, Universität Potsdam, Germany
Ziena Zeif
  • Hasso Plattner Institute, Universität Potsdam, Germany

Funding

This research was partially funded by the HPI Research School on Data Science and Engineering.
  • Zeif, Ziena: HPI Research School.

Cite As Get 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

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)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. 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. Google Scholar
  2. 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. Google Scholar
  3. 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. Google Scholar
  4. 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. Google Scholar
  5. 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.
  6. 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.
  7. Lester Randolph Ford and Delbert R Fulkerson. Maximal flow through a network. In Classic papers in combinatorics, pages 243-248. Springer, 2009. Google Scholar
  8. 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. Google Scholar
  9. 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. Google Scholar
  10. 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. Google Scholar
  11. 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. Google Scholar
  12. T Chiang Hu. Multi-commodity network flows. Operations research, 11(3):344-360, 1963. Google Scholar
  13. 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. Google Scholar
  14. 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. Google Scholar
  15. 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. Google Scholar
  16. 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. Google Scholar
  17. 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. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact