  This paper studies the fundamental problem of 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 and fast. This
scheduling problem has applications in traffic engineering in communication
networks and has recently received much attention in software-defined networks,
in which updates are distributed over an asynchronous network by a software
controller. However, existing algorithms for this problem either have a
super-polynomial runtime or only compute feasible schedules, which do not
provide any guarantees on the length of the rerouting schedule.
  This paper presents the first polynomial-time algorithm for computing
shortest update schedules to reroute flows in a congestion-free manner. We
contribute an almost tight characterization of the polynomial-time tractability
of the problem: We present the first polynomial-time solution for this problem
for two flows, but also show that even the question whether a feasible update
schedule exists, is already NP-hard for six flows.
  In fact, the presented algorithm runs in linear time and is hence not only
optimal in terms of scheduling but also asymptotically optimal in terms of
runtime.
