Document Open Access Logo

A Faster Algorithm for Recognizing Directed Graphs Invulnerable to Braess’s Paradox

Authors Akira Matsubayashi , Yushi Saito

PDF

File

Thumbnail PDF
PDF
OASIcs.ATMOS.2023.12.pdf
  • Filesize: 0.77 MB
  • 19 pages

Document Identifiers

Subject Classification

ACM Subject Classification
  • Theory of computation → Graph algorithms analysis
  • Theory of computation → Network flows
  • Mathematics of computing → Graph algorithms
  • Mathematics of computing → Network flows
Keywords
  • Braess’s paradox
  • series-parallel graph
  • route-induced graph
  • Nash flow

Metrics

Abstract

Braess’s paradox is a counterintuitive and undesirable phenomenon, in which for a given graph with prescribed source and sink vertices and cost functions for all edges, removal of edges decreases the cost of a Nash flow from source to sink. The problem of deciding if the phenomenon occurs is generally NP-hard. In this paper, we consider the problem of deciding if, for a given graph with prescribed source and sink vertices, Braess’s paradox does not occur for any cost functions. It is known that this problem can be solved in O(nm²) time for directed graphs, where n and m are the numbers of vertices and edges of the input graph, respectively. In this paper, we propose a faster O(m²) time algorithm solving this problem for directed graphs. Our approach is based on a simple implementation of a known characterization that the subgraph of a given graph induced by all source-sink paths is series-parallel. The faster running time is achieved by speeding up the simple implementation using another characterization that a certain structure is embedded in the given graph. Combined with a known technique, the proposed algorithm can also be used to design a faster O(km²) time algorithm for directed graphs with k source-sink pairs, which improves the previous O(knm²) time algorithm.

Cite As Get BibTex

Akira Matsubayashi and Yushi Saito. A Faster Algorithm for Recognizing Directed Graphs Invulnerable to Braess’s Paradox. In 23rd Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2023). Open Access Series in Informatics (OASIcs), Volume 115, pp. 12:1-12:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023) https://doi.org/10.4230/OASIcs.ATMOS.2023.12

Author Details

Akira Matsubayashi
  • Division of Electrical Engineering and Computer Science, Kanazawa University, Japan
Yushi Saito
  • Division of Electrical Engineering and Computer Science, Kanazawa University, Japan

Funding

  • Matsubayashi, Akira: This work was supported by JSPS KAKENHI Grant Number 23K10984.

Acknowledgements

The authors would like to thank the anonymous reviewers for their valuable comments.

References

  1. Stephen Alstrup, Dov Harel, Peter W. Lauridsen, and Mikkel Thorup. Dominators in linear time. SIAM Journal on Computing, 28(6):2117-2132, 1999. URL: https://doi.org/10.1137/S0097539797317263.
  2. Dietrich Braess. Über ein paradoxon aus der verkehrsplanung. Unternehmensforschung, 12:258-268, 1968. URL: https://doi.org/10.1007/BF01918335.
  3. Dietrich Braess, Anna Nagurney, and Tina Wakolbinger. On a paradox of traffic planning. Transportation Science, 39(4):446-450, 2005. URL: https://doi.org/10.1287/trsc.1050.0127.
  4. Adam L. Buchsbaum, Loukas Georgiadis, Haim Kaplan, Anne Rogers, Robert E. Tarjan, and Jeffery R. Westbrook. Linear-time algorithms for dominators and other path-evaluation problems. SIAM Journal on Computing, 38(4):1533-1573, 2008. URL: https://doi.org/10.1137/070693217.
  5. Adam L. Buchsbaum, Haim Kaplan, Anne Rogers, and Jeffery R. Westbrook. Corrigendum: A new, simpler linear-time dominators algorithm. ACM Transactions on Programming Languages and Systems, 27(3):383-387, 2005. URL: https://doi.org/10.1145/1065887.1065888.
  6. Pietro Cenciarelli, Daniele Gorla, and Ivano Salvo. Inefficiencies in network models: A graph-theoretic perspective. Information Processing Letters, 131:44-50, 2018. URL: https://doi.org/10.1016/j.ipl.2017.10.008.
  7. Pietro Cenciarelli, Daniele Gorla, and Ivano Salvo. A polynomial-time algorithm for detecting the possibility of Braess paradox in directed graphs. Algorithmica, 81:1535-1560, 2019. URL: https://doi.org/10.1007/s00453-018-0486-6.
  8. Xujin Chen, Zhuo Diao, and Xiaodong Hu. Network characterizations for excluding Braess’s paradox. Theory of Computing Systems, 59:747-780, 2016. URL: https://doi.org/10.1007/s00224-016-9710-4.
  9. Dario Fiorenza, Daniele Gorla, and Ivano Salvo. Polynomial recognition of vulnerable multi-commodities. Information Processing Letters, 179:106282, 2023. URL: https://doi.org/10.1016/j.ipl.2022.106282.
  10. Igal Milchtaich. Network topology and the efficiency of equilibrium. Games and Economic Behavior, 57(2):321-346, 2006. URL: https://doi.org/10.1016/j.geb.2005.09.005.
  11. Tim Roughgarden. Designing networks for selfish users is hard. In Proceedings of the 42nd Annual Symposium on Foundations of Computer Science, pages 472-481, 2001. URL: https://doi.org/10.1109/SFCS.2001.959923.
  12. Tim Roughgarden. Selfish Routing and the Price of Anarchy. The MIT Press, 2005. Google Scholar
  13. Tim Roughgarden. On the severity of Braess’s Paradox: Designing networks for selfish users is hard. Journal of Computer and System Sciences, 72(5):922-953, 2006. URL: https://doi.org/10.1016/j.jcss.2005.05.009.
  14. Robert Tarjan. Depth-first search and linear graph algorithms. SIAM Journal on Computing, 1(2):146-160, 1972. URL: https://doi.org/10.1137/0201010.
  15. Jacobo Valdes, Robert E. Tarjan, and Eugene L. Lawler. The recognition of series parallel digraphs. SIAM Journal on Computing, 11(2):298-313, 1982. URL: https://doi.org/10.1137/0211023.
Any Issues?
X

Feedback on the Current Page

CAPTCHA

Thanks for your feedback!

Feedback submitted to Dagstuhl Publishing

Could not send message

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