Network Topology That Excludes Braess's Paradox and Maintains Monotonicity in Flows Over Time
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.
Related
- Concurrent enforcement of polyconvexity and true-stress-true-strain monotonicity in incompressible isotropic hyperelasticity: application to neural network constitutive models
- Topology-Aware Integrated Sensing, Communication, Charging in Massive Low-Altitude Wireless Network
- The maximum spectral radius of uniform hypergraphs whose shadow excludes a complete or complete bipartite minor
- Support monotonicity and gap dynamics in one-dimensional MMD flows
- Monotonicity Property of Non-Archimedean Heat Equation
BibTeX
@misc{chen2026network,
title = {{Network Topology That Excludes Braess's Paradox and Maintains Monotonicity in Flows Over Time}},
author = {Xujin Chen and Xiyuan Deng and Changjun Wang},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.32738},
eprint = {2609.32738},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.32738},
}
RIS
TY - UNPB
TI - Network Topology That Excludes Braess's Paradox and Maintains Monotonicity in Flows Over Time
AU - Xujin Chen
AU - Xiyuan Deng
AU - Changjun Wang
PY - 2026
DA - 2026/09/26
PB - arXiv
DO - 10.48550/arxiv.2609.32738
UR - https://arxiv.org/abs/2609.32738
AB - 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.
ER -