DROPS

Document

APPROX

DOI: 10.4230/LIPIcs.APPROX/RANDOM.2022.55

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

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

Published in: LIPIcs, Volume 245, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2022)

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.

Cite as

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)

Copy BibTex To Clipboard

@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/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2022.55},
  URN =		{urn:nbn:de:0030-drops-171774},
  doi =		{10.4230/LIPIcs.APPROX/RANDOM.2022.55},
  annote =	{Keywords: Approximation Algorithms, Multicommodity Flow, Multicut}
}

Search Results

Documents authored by Mallek, Nadym

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

Abstract

Cite as

Thanks for your feedback!

Could not send message