2026-07-23T13:35:46Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:17177 2024-03-06T10:59:10Z ddc:004 open_access

A Primal-Dual Algorithm for Multicommodity Flows and Multicuts in Treewidth-2 Graphs Friedrich, Tobias Issac, Davis Kumar, Nikhil Mallek, Nadym Zeif, Ziena Approximation Algorithms Multicommodity Flow Multicut 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Tobias Friedrich and Davis Issac and Nikhil Kumar and Nadym Mallek and Ziena Zeif 2022 Is Part Of LIPIcs, Volume 245, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2022) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.APPROX/RANDOM.2022.55 urn:nbn:de:0030-drops-171774 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2022.55 eng https://creativecommons.org/licenses/by/4.0/legalcode