Unsplittable Flows in Planar GraphsOberseminar Discrete Optimization

by David Aleman Espinosa (University of Waterloo, Canada)

Monday Sep 1, 2025, 6:15 PM → 7:15 PM Europe/Berlin

Arithmeum, Lennéstr., 2 - Seminarraum (Arithmeum / Research Institute for Discrete Mathematics)

Given an undirected graph G=(V, E(G)) with edge capacities and multiple demand pairs {(s_i, t_i)} with associated demands {d_i}, the multicommodity flow problem asks for a simultaneous routing of all demands while respecting the edge capacities. The auxiliary demand graph

H=(V, E(H)) comprises an edge (s_i, t_i) for each demand pair. A multicommodity flow is called unsplittable if, for every demand pair, all the flow between its endpoints is routed along a single path.

Already in simple settings, such as the single-source setting (H a star), the existence of a feasible fractional flow does not imply the existence of an unsplittable flow. This leads to a natural question: given a feasible flow, does there exist an unsplittable flow that satisfies all the demands while violating the edge capacities up to a small additive term? A seminal result of Dinitz, Garg, and Goemans is that in the single-source setting, any feasible fractional flow can be converted into an unsplittable flow that violates the edge capacities by at most the maximum demand. The problem is significantly less understood outside of the single-source setting.

In this talk, we consider two natural settings arising from planar graphs:

1) Outerplanar instances, where G is outerplanar and H is arbitrary. We show that any feasible flow can be converted into an unsplittable flow that violates edge capacities by at most a constant times the maximum demand, for some constant smaller than 4. This extends a classical result of Schrijver, Seymour, and Winkler on instances with G a cycle, where they achieved a violation of at most three halves of the maximum demand. Joint work with Nikhil Kumar.

2) Fully planar instances, where G and H are such that G + H = (V, E(G) ∪ E(H) ) is planar. We achieve a violation of at most twice the maximum demand, and show that this bound is essentially tight. Joint work with Nikhil Kumar, Joseph Poremba, and Bruce Shepherd.

 

The Oberseminar takes place in the conference room, 2^nd floor. Participants are invited to have coffee or tea in the lounge before.