License: 
Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ICALP.2018.157
URN: urn:nbn:de:0030-drops-91613
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2018/9161/
Kupferman, Orna ;
Vardi, Gal
The Unfortunate-Flow Problem
Abstract
In the traditional maximum-flow 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 maximal-flow 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 maximal-flow 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 unfortunate-flow problem is co-NP-complete 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 no-loss 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 Unfortunate-Flow Problem}},
booktitle = {45th International Colloquium on Automata, Languages, and Programming (ICALP 2018)},
pages = {157:1--157:14},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-076-7},
ISSN = {1868-8969},
year = {2018},
volume = {107},
editor = {Ioannis Chatzigiannakis and Christos Kaklamanis and D{\'a}niel Marx and Donald Sannella},
publisher = {Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2018/9161},
URN = {urn:nbn:de:0030-drops-91613},
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 |
