Abstract
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 mincost 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 reroutableflow equivalent of an stcut 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 NPhard, even when all capacities are in {1, 2}. However, the tightening can be used to get a 2approximation 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 NPhard to compute a maximal integral flow even for unit capacities, we devise a surprisingly simple combinatorial algorithm that finds a halfintegral 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.
BibTeX  Entry
@InProceedings{matuschke_et_al:LIPIcs:2017:7446,
author = {Jannik Matuschke and S. Thomas McCormick and Gianpaolo Oriolo},
title = {{Rerouting Flows When Links Fail}},
booktitle = {44th International Colloquium on Automata, Languages, and Programming (ICALP 2017)},
pages = {89:189:13},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959770415},
ISSN = {18688969},
year = {2017},
volume = {80},
editor = {Ioannis Chatzigiannakis and Piotr Indyk and Fabian Kuhn and Anca Muscholl},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2017/7446},
URN = {urn:nbn:de:0030drops74466},
doi = {10.4230/LIPIcs.ICALP.2017.89},
annote = {Keywords: network flows, network interdiction, robust optimization}
}
Keywords: 

network flows, network interdiction, robust optimization 
Collection: 

44th International Colloquium on Automata, Languages, and Programming (ICALP 2017) 
Issue Date: 

2017 
Date of publication: 

07.07.2017 