The unsplittable transshipment problem is a strongly NP-complete network flow problem inspired by the well-studied Single-Source Unsplittable Flow (SSUF) problem. It involves routing a single commodity from sources to sinks in a capacity-constrained network, using at most one path for each source-sink pair. The unsplittable flow problem has applications in network design, logistics, and telecommunications, but its transshipment variant is unexplored in the literature.

This talk addresses the unsplittable transshipment problem in directed graphs, proving its strong NP-completeness even under uniform flow conditions (rendering it “harder” than the SSUF problem). We show that converting feasible fractional transshipments to an unsplittable form only requires arc-capacity violations up to the maximum demand of any sink. We propose a generalization of Dinitz Garg Goeman's Algorithm [1] to achieve the aforementioned capacity violations, and restrict the total number of paths to the number of sources plus the number of sinks minus one.

References
[1] Y. Dinitz, N. Garg, and M. X. Goemans. “On The Single-Source Un-
splittable Flow Problem”. In: Combinatorica 19 (1999), pp. 17–41. doi:
10.1007/s004930050043..