Creative Commons Attribution 4.0 license (CC BY 4.0)when quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.APPROX/RANDOM.2022.55
URN: urn:nbn:de:0030-drops-171774
URL: https://drops.dagstuhl.de/opus/volltexte/2022/17177/
Friedrich, Tobias ; Issac, Davis ; Kumar, Nikhil ; Mallek, Nadym ; Zeif, Ziena
A Primal-Dual Algorithm for Multicommodity Flows and Multicuts in Treewidth-2 Graphs
| pdf-format: |
|
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.
BibTeX - Entry
@InProceedings{friedrich_et_al:LIPIcs.APPROX/RANDOM.2022.55,
author = {Friedrich, Tobias and Issac, Davis and Kumar, Nikhil and Mallek, Nadym and Zeif, Ziena},
title = {{A Primal-Dual Algorithm for Multicommodity Flows and Multicuts in Treewidth-2 Graphs}},
booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2022)},
pages = {55:1--55:18},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-249-5},
ISSN = {1868-8969},
year = {2022},
volume = {245},
editor = {Chakrabarti, Amit and Swamy, Chaitanya},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2022/17177},
URN = {urn:nbn:de:0030-drops-171774},
doi = {10.4230/LIPIcs.APPROX/RANDOM.2022.55},
annote = {Keywords: Approximation Algorithms, Multicommodity Flow, Multicut}
}
| Keywords: | Approximation Algorithms, Multicommodity Flow, Multicut | |
| Seminar: | Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2022) | |
| Issue date: | 2022 | |
| Date of publication: | 15.09.2022 |
