  We introduce and investigate reroutable flows, a robust version of network
flows in which link failures can be mitigated by rerouting the affected flow.
Given a capacitated network, a path flow is reroutable if after failure of an
arbitrary arc, we can reroute the interrupted flow from the tail of that arc to
the sink, without modifying the flow that is not affected by the failure.
Similar types of restoration, which are often termed "local", were previously
investigated in the context of network design, such as min-cost capacity
planning. In this paper, our interest is in computing maximum flows under this
robustness assumption. An important new feature of our model, distinguishing it
from existing max robust flow models, is that no flow can get lost in the
network.
  We also study a tightening of reroutable flows, called strictly reroutable
flows, making more restrictive assumptions on the capacities available for
rerouting. For both variants, we devise a reroutable-flow equivalent of an
s-t-cut and show that the corresponding max flow/min cut gap is bounded by 2.
It turns out that a strictly reroutable flow of maximum value can be found
using a compact LP formulation, whereas the problem of finding a maximum
reroutable flow is NP-hard, even when all capacities are in {1, 2}. However,
the tightening can be used to get a 2-approximation for reroutable flows. This
ratio is tight in general networks, but we show that in the case of unit
capacities, every reroutable flow can be transformed into a strictly reroutable
flow of same value. While it is NP-hard to compute a maximal integral flow even
for unit capacities, we devise a surprisingly simple combinatorial algorithm
that finds a half-integral strictly reroutable flow of value 1, or certifies
that no such solutions exits. Finally, we also give a hardness result for the
case of multiple arc failures.
