Hafif Güvenilir Yayılıcılar

Özet (abstract)

Abstract. A [Formula: see text] -reliable spanner of a metric space [Formula: see text] is a (dominating) graph [Formula: see text] such that for any possible failure set [Formula: see text], there is a set [Formula: see text] just slightly larger than [Formula: see text], and all distances between pairs in [Formula: see text] are (approximately) preserved in [Formula: see text]. Recently, there have been several works on sparse reliable spanners in various settings, but so far, the weight of such spanners has not been analyzed at all. In this work, we initiate the study of light reliable spanners whose weight is proportional to that of the minimum spanning tree (MST) of [Formula: see text]. We first observe that unlike sparsity, the lightness of any deterministic reliable spanner is huge, even for the metric of the simple path graph. Therefore, randomness must be used: An oblivious reliable spanner is a distribution over spanners, and the bound on [Formula: see text] holds in expectation. We devise an oblivious [Formula: see text]-reliable [Formula: see text]-spanner for any [Formula: see text]-HST whose lightness is [Formula: see text]. We demonstrate a matching [Formula: see text] lower bound on the lightness (for any finite stretch). We also note that any stretch below 2 must incur linear lightness. For general metrics, doubling metrics, and metrics arising from minor-free graphs, we construct light tree covers in which every tree is a [Formula: see text]-HST of low weight. Combining these covers with our results for [Formula: see text]-HSTs, we obtain oblivious reliable light spanners for these metric spaces, with nearly optimal parameters. In particular, for doubling metrics, we get an oblivious [Formula: see text]-reliable [Formula: see text]-spanner with lightness [Formula: see text], which is best possible (up to lower-order terms).

Yazarların özeti; kaynağından alınmıştır. SIAM Journal on Discrete Mathematics, 2026 · DOI ↗