Document Open Access Logo

The Unfortunate-Flow Problem

Authors Orna Kupferman, Gal Vardi

PDF
Thumbnail PDF

File

LIPIcs.ICALP.2018.157.pdf
  • Filesize: 0.65 MB
  • 14 pages

Document Identifiers

Author Details

Orna Kupferman
  • School of Computer Science and Engineering, The Hebrew University, Israel
Gal Vardi
  • School of Computer Science and Engineering, The Hebrew University, Israel

Cite As Get BibTex

Orna Kupferman and Gal Vardi. The Unfortunate-Flow Problem. In 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 107, pp. 157:1-157:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018) https://doi.org/10.4230/LIPIcs.ICALP.2018.157

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.

Subject Classification

ACM Subject Classification
  • Mathematics of computing → Network flows
Keywords
  • Flow Network
  • Graph Algorithms
  • Games

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

Related Versions

References

  1. R.K. Ahuja, T.L. Magnanti, and J.B. Orlin. Network flows: Theory, algorithms, and applications. Prentice Hall Englewood Cliffs, 1993. Google Scholar
  2. C. Bazgan, M. Chopin, M. Cygan, M.R. Fellows, F. V. Fomin, and E. Leeuwen. Parameterized complexity of firefighting. Journal of Computer and Systems Science, 80(7):1285-1297, 2014. Google Scholar
  3. J. Choudhari, A. Dasgupta, N. Misra, and M.S. Ramanujan. Saving critical nodes with firefighters is FPT. In Proc. 44th Int. Colloq. on Automata, Languages, and Programming, volume 80 of LIPIcs, pages 135:1-135:13, 2017. Google Scholar
  4. T.H. Cormen, C.E. Leiserson, and R.L. Rivest. Introduction to Algorithms. MIT Press and McGraw-Hill, 1990. Google Scholar
  5. E.A. Dinic. Algorithm for solution of a problem of maximum flow in a network with power estimation. Soviet Math. Doll, 11(5):1277-1280, 1970. English translation by RF. Rinehart. Google Scholar
  6. J. Edmonds and R.M. Karp. Theoretical improvements in algorithmic efficiency for network flow problems. Journal of the ACM, 19(2):248-264, 1972. Google Scholar
  7. S. Even, A. Itai, and A. Shamir. On the complexity of timetable and multicommodity flow problems. SIAM Journal on Computing, 5(4):691-703, 1976. Google Scholar
  8. L.R. Ford and D.R. Fulkerson. Maximal flow through a network. Canadian journal of Mathematics, 8(3):399-404, 1956. Google Scholar
  9. L.R. Ford and D.R. Fulkerson. Flows in networks. Princeton Univ. Press, Princeton, 1962. Google Scholar
  10. A.V. Goldberg, É. Tardos, and R.E. Tarjan. Network flow algorithms. Technical report, DTIC Document, 1989. Google Scholar
  11. A.V. Goldberg and R.E. Tarjan. A new approach to the maximum-flow problem. Journal of the ACM, 35(4):921-940, 1988. Google Scholar
  12. S. Guha, O. Kupferman, and G. Vardi. Multi-player flow games. In Proc. 17th International Conference on Autonomous Agents and Multiagent Systems, 2018. Google Scholar
  13. S. Keren, A. Gal, and E. Karpas. Goal recognition design for non optimal agents. In Proc. 29th AAAI conference, pages 3298-3304, 2015. Google Scholar
  14. O. Kupferman, G. Vardi, and M.Y. Vardi. Flow games. In Proc. 37th Conf. on Foundations of Software Technology and Theoretical Computer Science, volume 93 of Leibniz International Proceedings in Informatics (LIPIcs), pages 38:38-38:16, 2017. Google Scholar
  15. A. Madry. Computing maximum flow with augmenting electrical flows. In Foundations of Computer Science (FOCS), 2016 IEEE 57th Annual Symposium on, pages 593-602. IEEE, 2016. Google Scholar
  16. L. Qingsong, G. Betsy, and S. Shashi. Capacity constrained routing algorithms for evacuation planning: A summary of results. In International Symposium on Spatial and Temporal Databases, pages 291-307. Springer, 2005. Google Scholar
  17. E.D. Sontag. Real addition and the polynomial hierarchy. Information Processing Letters, 20(3):115-120, 1985. Google Scholar
  18. É. Tardos. A strongly polynomial minimum cost circulation algorithm. Combinatorica, 5(3):247-255, 1985. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact