Abstract
In the traditional maximumflow problem, the goal is to transfer maximum flow in a network by directing, in each vertex in the network, incoming flow into outgoing edges. The problem is one of the most fundamental problems in TCS, with application in numerous domains. The fact a maximalflow algorithm directs the flow in all the vertices of the network corresponds to a setting in which the authority has control in all vertices. Many applications in which the maximalflow problem is applied involve an adversarial setting, where the authority does not have such a control.
We introduce and study the unfortunate flow problem, which studies the flow that is guaranteed to reach the target when the edges that leave the source are saturated, yet the most unfortunate decisions are taken in the vertices. When the incoming flow to a vertex is greater than the outgoing capacity, flow is lost. The problem models evacuation scenarios where traffic is stuck due to jams in junctions and communication networks where packets are dropped in overloaded routers.
We study the theoretical properties of unfortunate flows, show that the unfortunateflow problem is coNPcomplete and point to polynomial fragments. We introduce and study interesting variants of the problem: integral unfortunate flow, where the flow along edges must be integral, controlled unfortunate flow, where the edges from the source need not be saturated and may be controlled, and noloss controlled unfortunate flow, where the controlled flow must not be lost.
BibTeX  Entry
@InProceedings{kupferman_et_al:LIPIcs:2018:9161,
author = {Orna Kupferman and Gal Vardi},
title = {{The UnfortunateFlow Problem}},
booktitle = {45th International Colloquium on Automata, Languages, and Programming (ICALP 2018)},
pages = {157:1157:14},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959770767},
ISSN = {18688969},
year = {2018},
volume = {107},
editor = {Ioannis Chatzigiannakis and Christos Kaklamanis and D{\'a}niel Marx and Donald Sannella},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2018/9161},
URN = {urn:nbn:de:0030drops91613},
doi = {10.4230/LIPIcs.ICALP.2018.157},
annote = {Keywords: Flow Network, Graph Algorithms, Games}
}
Keywords: 

Flow Network, Graph Algorithms, Games 
Collection: 

45th International Colloquium on Automata, Languages, and Programming (ICALP 2018) 
Issue Date: 

2018 
Date of publication: 

04.07.2018 