Dynamic Algorithms for Detecting Vulnerability to the Braess Paradox in Multi-Commodity Networks

Braess paradox is a well known and largely studied phenomenon in traffic networks. Determining whether the paradox occurs has been shown to be NP-hard. A purely graph-theoretic characterization of this phenomenon, introduced by Roughgarden in 2006 under the name of vulnerability, provides an alternative viewpoint. The offline vulnerability problem can be solved in polynomial time, with the fastest known algorithm running in 𝑂(𝑚2) time for single commodity and 𝑂(𝑘𝑚2) for 𝑘-commodity networks. We summarize our two recent works, in which we developed dynamic amortized 𝑂(𝑚)-time algorithms for detecting vulnerability under edge insertions and deletions, and discuss the techniques underlying their design. As a new contribution, we extend these results to 𝑘-commodity networks, obtaining amortized 𝑂(𝑘𝑚)-time dynamic algorithms.