2026-07-23T22:07:01Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:18773 2024-03-06T10:32:14Z ddc:004 open_access

A Faster Algorithm for Recognizing Directed Graphs Invulnerable to Braess’s Paradox Matsubayashi, Akira Saito, Yushi Braess’s paradox series-parallel graph route-induced graph Nash flow 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Akira Matsubayashi and Yushi Saito 2023 Is Part Of OASIcs, Volume 115, 23rd Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2023) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/OASIcs.ATMOS.2023.12 urn:nbn:de:0030-drops-187738 https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.ATMOS.2023.12 eng https://creativecommons.org/licenses/by/4.0/legalcode