Expander Routing under Adversarial Deletions via Temporal Aggregation

Abstract

In expander routing, we seek to establish paths in the expander graph between given source-target pairs while minimizing both dilation (maximum path length) and congestion (maximum edge load). We study this problem in a decremental dynamic setting where the underlying graph remains an expander despite ongoing edge deletions, and source-target pairs can be added or removed. Our goal is to maintain paths under these updates while keeping dilation and congestion low and performing low computation per update. We present a randomized algorithm that maintains paths with polylogarithmic dilation and congestion against an adaptive adversary, while incurring only polylogarithmic amortized computation per update, all with high probability. Our approach leverages a recent technique called Temporal Aggregation to maintain a collection of low-congestion, low-dilation random walks resilient to adaptive adversaries.

The authors’ abstract, as arXiv lists it. arXiv’s listings, abstracts included, are free for anyone to reuse.

More in Data Structures & Algorithms

• arXiv preprint · 2 November 2026

  Efficient Proper Agnostic Learning of Halfspaces

  Anindya De, Elchanan Mossel, Shivam Nadimpalli and 1 other
• arXiv preprint · 3 November 2026

  A Constant-Factor Approximation for Capacitated Facility Location with Outliers

  Rajni Dabas
• arXiv preprint · 2 November 2026

  Submodularity Is Barely Testable

  Diptaksho Palit and Yuichi Yoshida
• arXiv preprint · 3 November 2026

  Semidirect sums of tensors and the matrix multiplication exponent

  Baitian Li
• arXiv preprint · 2 November 2026

  Generalized Flows over Time: Complexity, Structure and Algorithm

  Siyuan Chen, Shengminjie Chen, Suixiang Gao and 3 others

All new papers in Data Structures & Algorithms