Unsplittable Flow Cut Gap in Undirected Graphs

We consider multicommodity flows in undirected graphs. An instance consists of an edgecapacitated graph $G$, called the supply graph, and a set of source-sink pairs with associated demands (commodities), defining a demand graph $H$. An instance is said to be feasible if there exists a flow that routes all demands while respecting the edge capacities. In many applications, it is further required that the entire demand of each commodity be routed along a single path; this is known as the unsplittable multicommodity flow problem. We study conditions under which the existence of a feasible (splittable) flow implies the existence of an unsplittable flow that does not significantly violate edge capacities.