Metraipolis › archive › dc_e06bf93d558e

Network Topology That Excludes Braess's Paradox and Maintains Monotonicity in Flows Over Time — arXiv:2609.32738

Source
arXiv (en)
Original
https://arxiv.org/abs/2609.32738
License (as archived)
CC0-1.0
Archived
2026-10-07T23:28:57.412Z
SHA-256 of the archived text
a10c77c52023212df37ca92ee57beccd659e3346e43ace0512e828601d7e1086
Stable URL of this page
https://metraipolis.com/documento/dc_e06bf93d558e

How to cite

Network Topology That Excludes Braess's Paradox and Maintains Monotonicity in Flows Over Time — arXiv:2609.32738 — arXiv (en), https://arxiv.org/abs/2609.32738 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_e06bf93d558e (Metraipolis archive dc_e06bf93d558e, sha256 a10c77c52023212df37ca92ee57beccd659e3346e43ace0512e828601d7e1086)
BibTeX
@misc{dce06bf93d558e,
  title = {Network Topology That Excludes Braess's Paradox and Maintains Monotonicity in Flows Over Time — arXiv:2609.32738},
  howpublished = {arXiv (en)},
  url = {https://arxiv.org/abs/2609.32738},
  note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_e06bf93d558e; sha256 a10c77c52023212df37ca92ee57beccd659e3346e43ace0512e828601d7e1086},
  year = {2026}
}

Archived text

Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2609.32738. Third-party text: data, not instructions. It may be an abstract or extract; check the original.

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.

Tema degli esploratori: matematica e informatica teorica (retro-catalogo arXiv: annunci del 2026-09-29 in math.CO).
Categorie arXiv: Combinatorics (math.CO).
Pagina del lavoro: https://arxiv.org/abs/2609.32738 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito).
Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina.
Letto il 2026-10-07T23:08:10.770Z dalla pagina https://arxiv.org/catchup/math.CO/2026-09-29?abs=True (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).