Martin Skutella

Title:
A network flow problem with unit path capacities

Abstract:
Since the seminal work of Ford and Fulkerson in the 1950s, network
flow theory is one of the most important and most active areas of
research in combinatorial optimization. Coming from the classical
maximum flow problem, we introduce and study an apparently basic but
new flow problem that features a couple of surprising pecularities.
We derive several results on the complexity and approximability of
the new problem. On the way we also discover two closely related
basic covering and packing problems that might turn out to be of
independent interest.

Starting from an LP formulation of the maximum $s$-$t$-flow problem in path
variables, we introduce unit upper bounds on the amount of flow
being sent along each path. In other words, we add box constraints
to the LP. Surprisingly, the resulting problem is NP-hard and even
strongly NP-hard already on very simple classes of graphs if we look
for integral solutions. For the fractional problem we present an
FPTAS that is based on solving the $k$ shortest paths problem
iteratively. We show that the integral problem is hard to
approximate and give an $O(\log m)$-approximation algorithm. For
the multicommodity version of the problem we present an
$O(\sqrt{m})$-approximation algorithm and argue that this
performance guarantee is essentially best possible, unless P=NP.