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.
A Faster Algorithm for Recognizing Directed Graphs Invulnerable to Braess’s Paradox
2023-08-31
19 pages , 810783 byte
OASIcs, Vol. 115, 23rd Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2023), pages 12:1-12:19
Conference paper
Electronic Resource
English
Airway network management using Braess’s Paradox
Elsevier | 2019
|Braess's paradox of traffic flow
Elsevier | 1970
|Characterizing Braess's paradox for traffic networks
IEEE | 2001
|The Braess's Paradox in Dynamic Traffic
IEEE | 2022
|Characterizing Braess's Paradox for Traffic Networks
British Library Conference Proceedings | 2001
|