OpenAlex ·
Network Topology That Excludes Braess's Paradox and Maintains Monotonicity in Flows Over Time
- Published
- Source
- OpenAlex
- Published in
- arXiv (Cornell University)
- DOI
- 10.48550/arxiv.2609.32738
- Original
- Read it at the publisher
- Topics
Abstract
In the game of \emph{flow over time}, infinitesimal flow particles aim to travel from a source to a sink in a network as quickly as possible. Under the Vickrey bottleneck model, the congestion effects on network edges are captured through FIFO queues, which arise when the inflow into an edge exceeds its capacity. This work addresses two open conjectures about the game: 1) the characterization of networks that are immune to Braess's paradox, and 2) the monotonicity relationship between the network inflow rate and the overall flow makespan. We show that a single class of network topologies, called \emph{chains of bipolar pseudo-arborescences} (\emph{BPAs}), fully resolves the first conjecture and yields partial progress on the second. Chains of BPAs constitute precisely the cases left open by Macko et al.~(2013) in their study of Braess's paradox for flow over time. By structurally characterizing the dynamic evolution of Nash flows over time on such networks, we prove that removing edges from these networks never decreases the maximum equilibrium latency. Combined with the results of Macko et al., this establishes a necessary and sufficient condition: \emph{a network does not admit Braess's paradox for flow over time if and only if it is a chain of BPAs}, thereby resolving their conjecture. Furthermore, we confirm the monotonicity conjecture of Correa et al.~(2021) for all chains of BPAs. This result strictly generalizes the previously known monotonicity for chains of parallel paths under uniform inflows.
The authors’ abstract, as arXiv lists it. arXiv’s listings, abstracts included, are free for anyone to reuse.
Read it on ReadSearch
Each opens after you create an account, and brings you back to this paper.
More in Computational Complexity
A 51-Addition Alternative-Basis Kernel for Rank-23 $3\times3$ Matrix Multiplication
An EPTAS for Offline Temporary Tasks Assignment on Few Machines
Parity Tests under Ties: A One-Test Lifting Theorem
The Fully Depolarizing Noise Conjecture for Entangled Physical States: A Twenty-Year Perspective
Higher-Order Mean-Field Control Barrier Functions
Get the few papers worth your time in Computational Complexity every morning.
ReadSearch reads the new papers in your field each day and brings you the few worth reading, each with its key finding in a sentence.