License: 
Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/OASIcs.ATMOS.2023.12
URN: urn:nbn:de:0030-drops-187738
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2023/18773/
Matsubayashi, Akira ;
Saito, Yushi
A Faster Algorithm for Recognizing Directed Graphs Invulnerable to Braess’s Paradox
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.
BibTeX - Entry
@InProceedings{matsubayashi_et_al:OASIcs.ATMOS.2023.12,
author = {Matsubayashi, Akira and Saito, Yushi},
title = {{A Faster Algorithm for Recognizing Directed Graphs Invulnerable to Braess’s Paradox}},
booktitle = {23rd Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2023)},
pages = {12:1--12:19},
series = {Open Access Series in Informatics (OASIcs)},
ISBN = {978-3-95977-302-7},
ISSN = {2190-6807},
year = {2023},
volume = {115},
editor = {Frigioni, Daniele and Schiewe, Philine},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2023/18773},
URN = {urn:nbn:de:0030-drops-187738},
doi = {10.4230/OASIcs.ATMOS.2023.12},
annote = {Keywords: Braess’s paradox, series-parallel graph, route-induced graph, Nash flow}
}
|
Keywords: |
|
Braess’s paradox, series-parallel graph, route-induced graph, Nash flow |
|
Collection: |
|
23rd Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2023) |
|
Issue Date: |
|
2023 |
|
Date of publication: |
|
31.08.2023 |
