2026-09-08T01:22:02Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:26400 2026-09-05T19:42:18Z ddc:004 open_access

Pinning on Tight Cuts: Improved Algorithm and Bounds for Unsplittable Multicommodity Flows in Outerplanar Graphs Alemán Espinosa, David Schlomberg, Niklas Unsplittable Flows Multicommodity Flows Planar Graphs The multicommodity flow problem in an undirected capacitated graph G is specified by a set of source-sink pairs with nonnegative demands. A flow is feasible if it routes all demands without exceeding the edge capacities, and it is unsplittable if it routes each demand along a single path. Let α be the smallest value such that the existence of a feasible flow implies the existence of an unsplittable flow that exceeds the edge capacities by at most + α d_max. Schrijver, Seymour, and Winkler showed that α ∈ [1.01, 1.5] if G is a cycle. These bounds were ultimately improved to α ∈ [1.1, 1.3] by Skutella and Däubel. Recently, Alemán Espinosa and Kumar extended this constant upper bound to the broader class of outerplanar graphs, and showed that if G is outerplanar then α ≤ 3.6. We show that α ∈ [4/3,2] if G is outerplanar. We introduce a novel technique that considers the global parameters of the instance, and that may be useful in other (more general) settings where the cut-condition is sufficient, or nearly sufficient, for the existence of a feasible flow. Schloss Dagstuhl – Leibniz-Zentrum für Informatik David Alemán Espinosa and Niklas Schlomberg 2026 Is Part Of LIPIcs, Volume 374, 53rd International Colloquium on Automata, Languages, and Programming (ICALP 2026) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ICALP.2026.11 urn:nbn:de:0030-drops-264008 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2026.11 eng https://creativecommons.org/licenses/by/4.0/legalcode