  Changing a given configuration in a graph into another one is known as a re-
configuration problem. Such problems have recently received much interest in
the context of algorithmic graph theory. We initiate the theoretical study of
the following reconfiguration problem: How to reroute $k$ unsplittable flows of
a certain demand in a capacitated network from their current paths to their
respective new paths, in a congestion-free manner? This problem finds immediate
applications, e.g., in traffic engineering in computer networks. We show that
the problem is generally NP-hard already for $k = 2$ flows, which motivates us
to study rerouting on a most basic class of flow graphs, namely DAGs.
Interestingly, we find that for general $k$, deciding whether an unsplittable
multi-commodity flow rerouting schedule exists, is NP-hard even on DAGs. Both
NP-hardness proofs are non-trivial. Our main contribution is a polynomial-time
(fixed parameter tractable) algorithm to solve the route update problem for a
bounded number of flows on DAGs. At the heart of our algorithm lies a novel
decomposition of the flow network that allows us to express and resolve
reconfiguration dependencies among flows.
