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.


    Access

    Download


    Export, share and cite



    Title :

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


    Contributors:


    Publication date :

    2023-08-31


    Size :

    19 pages , 810783 byte


    Remarks:

    OASIcs, Vol. 115, 23rd Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2023), pages 12:1-12:19





    Type of media :

    Conference paper


    Type of material :

    Electronic Resource


    Language :

    English





    Airway network management using Braess’s Paradox

    Ma, Chunyao / Cai, Qing / Alam, Sameer et al. | Elsevier | 2019


    Braess's paradox of traffic flow

    Murchland, J.D. | Elsevier | 1970


    Characterizing Braess's paradox for traffic networks

    Hagstrom, J.N. / Abrams, R.A. | IEEE | 2001


    The Braess's Paradox in Dynamic Traffic

    Zhuang, Dingyi / Huang, Yuzhu / Jayawardana, Vindula et al. | IEEE | 2022


    Characterizing Braess's Paradox for Traffic Networks

    Hagstrom, J. N. / Abrams, R. A. / IEEE | British Library Conference Proceedings | 2001