arXiv:2611.03457 · v1

Expander Routing under Adversarial Deletions via Temporal Aggregation

首次提交 2026-11-03 01:01

版本更新 2026-11-03 01:01

雷达观测 2026-11-04 23:41

摘要

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.