DROPS

Document

Track A: Algorithms, Complexity and Games

DOI: 10.4230/LIPIcs.ICALP.2026.11

Pinning on Tight Cuts: Improved Algorithm and Bounds for Unsplittable Multicommodity Flows in Outerplanar Graphs

Authors: David Alemán Espinosa and Niklas Schlomberg

Published in: LIPIcs, Volume 374, 53rd International Colloquium on Automata, Languages, and Programming (ICALP 2026)

Abstract

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.

Cite as

David Alemán Espinosa and Niklas Schlomberg. Pinning on Tight Cuts: Improved Algorithm and Bounds for Unsplittable Multicommodity Flows in Outerplanar Graphs. In 53rd International Colloquium on Automata, Languages, and Programming (ICALP 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 374, pp. 11:1-11:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{alemanespinosa_et_al:LIPIcs.ICALP.2026.11,
  author =	{Alem\'{a}n Espinosa, David and Schlomberg, Niklas},
  title =	{{Pinning on Tight Cuts: Improved Algorithm and Bounds for Unsplittable Multicommodity Flows in Outerplanar Graphs}},
  booktitle =	{53rd International Colloquium on Automata, Languages, and Programming (ICALP 2026)},
  pages =	{11:1--11:23},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-428-4},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{374},
  editor =	{Bhattacharya, Sayan and Nanongkai, Danupon and Benedikt, Michael and Puppis, Gabriele},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2026.11},
  URN =		{urn:nbn:de:0030-drops-264008},
  doi =		{10.4230/LIPIcs.ICALP.2026.11},
  annote =	{Keywords: Unsplittable Flows, Multicommodity Flows, Planar Graphs}
}

Document

Track A: Algorithms, Complexity and Games

DOI: 10.4230/LIPIcs.ICALP.2024.122

An Improved Integrality Gap for Disjoint Cycles in Planar Graphs

Authors: Niklas Schlomberg

Published in: LIPIcs, Volume 297, 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)

Abstract

We present a new greedy rounding algorithm for the Cycle Packing Problem for uncrossable cycle families in planar graphs. This improves the best-known upper bound for the integrality gap of the natural packing LP to a constant slightly less than 3.5. Furthermore, the analysis works for both edge- and vertex-disjoint packing. The previously best-known constants were 4 for edge-disjoint and 5 for vertex-disjoint cycle packing. This result also immediately yields an improved Erdős-Pósa ratio: for any uncrossable cycle family in a planar graph, the minimum number of vertices (edges) needed to hit all cycles in the family is less than 8.38 times the maximum number of vertex-disjoint (edge-disjoint, respectively) cycles in the family. Some uncrossable cycle families of interest to which the result can be applied are the family of all cycles in a directed or undirected graph, in undirected graphs also the family of all odd cycles and the family of all cycles containing exactly one edge from a specified set of demand edges. The last example is an equivalent formulation of the fully planar Disjoint Paths Problem. Here the Erdős-Pósa ratio translates to a ratio between integral multi-commodity flows and minimum cuts.

Cite as

Niklas Schlomberg. An Improved Integrality Gap for Disjoint Cycles in Planar Graphs. In 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 297, pp. 122:1-122:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{schlomberg:LIPIcs.ICALP.2024.122,
  author =	{Schlomberg, Niklas},
  title =	{{An Improved Integrality Gap for Disjoint Cycles in Planar Graphs}},
  booktitle =	{51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)},
  pages =	{122:1--122:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-322-5},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{297},
  editor =	{Bringmann, Karl and Grohe, Martin and Puppis, Gabriele and Svensson, Ola},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2024.122},
  URN =		{urn:nbn:de:0030-drops-202651},
  doi =		{10.4230/LIPIcs.ICALP.2024.122},
  annote =	{Keywords: Cycle packing, planar graphs, disjoint paths}
}

Search Results

Documents authored by Schlomberg, Niklas

Pinning on Tight Cuts: Improved Algorithm and Bounds for Unsplittable Multicommodity Flows in Outerplanar Graphs

Abstract

Cite as

An Improved Integrality Gap for Disjoint Cycles in Planar Graphs

Abstract

Cite as

Thanks for your feedback!

Could not send message