Project
AA-Mobil-2
Unsplittable Flows
Project Heads
Martin Skutella, Philipp Warode
Project Members
Srinwanti Debgupta
Project Duration
01.07.2025 – 30.06.2028
Located at
TU Berlin
Description
Network flow theory concerns the optimal routing of commodities through networks and is fundamental to a wide range of application fields such as traffic, logistics, and computer networking. In many practical scenarios, splitting a commodity across multiple paths may degrade the quality of service, increase system complexity, or be simply infeasible. This motivates unsplittable multiflows. Here, for a given digraph with source-sink pairs, the demand of every commodity must be sent along a single path from its source to its sink. This project aims to advance our fundamental and algorithmic understanding of various unsplittable flow problems.
While classical network flow models allow splitting, unsplittable flows introduce additional constraints that significantly increase computational complexity. Understanding these challenges is essential for designing efficient and reliable routing systems.
Core Research Questions
Many unsplittable flow problems are NP-complete, meaning that no efficient solution methods are known for all cases.
The project aims to improve both the theoretical understanding and algorithmic solutions of unsplittable flow problems. A central challenge is transforming a fractional flow (where splitting is allowed) into an unsplittable one while controlling deviations.
Research Areas
Integral Multiflows & Cut Conditions
Investigates when flows can be routed integrally (without splitting) based on structural properties of the network. A central concept is the cut condition, which compares network capacity with demand across partitions.
Unsplittable Transshipments
Extends the model to multiple sources and sinks. Each source-sink pair must still use a single path, but routing is more flexible overall. The goal is to design efficient approximation algorithms for:
- Minimizing congestion
- Reducing the number of routing rounds
- Maximizing routed demand
Path-Based Augmentation Algorithms
Develops new techniques to iteratively improve routing solutions by modifying paths. These methods aim to be more flexible and practical than classical approaches, with promising empirical performance.
Related Publications
- Unsplittable Transshipments ()
ICALP 2026 – Proc. 53rd International Colloquium on Automata, Languages and Programming. - Integer and Unsplittable Multiflows in Series-Parallel Digraphs ()
IPCO 2025 – Proc. 26th Conference on Integer Programming and Combinatorial Optimization, Springer, pp. 427–441.
Selected Pictures
Please insert any kind of pictures (photos, diagramms, simulations, graphics) related to the project in the above right field (Image with Text), by choosing the green plus image on top of the text editor. (You will be directed to the media library where you can add new files.)
(We need pictures for a lot of purposes in different contexts, like posters, scientific reports, flyers, website,…
Please upload pictures that might be just nice to look at, illustrate, explain or summarize your work.)
As Title in the above form please add a copyright.
And please give a short description of the picture and the context in the above textbox.
Don’t forget to press the “Save changes” button at the bottom of the box.
If you want to add more pictures, please use the “clone”-button at the right top of the above grey box.