Partially Optimal Edge Fault-Tolerant Spanners

MaRDI QIDQ6361312zbMATH OpenFDO

Authors Greg Bodwin, Michael Dinitz, Caleb Robelle

Publication date 22 February 2021

Abstract: Recent work has established that, for every positive integer $k$, every $n$-node graph has a $(2k-1)$-spanner on $O(f^{1-1/k}{n}^{1+1/k})$ edges that is resilient to $f$ edge or vertex faults. For vertex faults, this bound is tight. However, the case of edge faults is not as well understood: the best known lower bound for general $k$ is $Omega(f^{frac12-frac12k}{n}^{1+1/k}+fn)$. Our main result is to nearly close this gap with an improved upper bound, thus separating the cases of edge and vertex faults. For odd $k$, our new upper bound is $O_k(f^{frac12-frac12k}{n}^{1+1/k}+fn)$, which is tight up to hidden $poly(k)$ factors. For even $k$, our new upper bound is $O_k(f^{1/2}{n}^{1+1/k}+fn)$, which leaves a gap of $poly(k)f^{1/(2k)}$. Our proof is an analysis of the fault-tolerant greedy algorithm, which requires exponential time, but we also show that there is a polynomial-time algorithm which creates edge fault tolerant spanners that are larger only by factors of $k$.

This page was built for publication: Partially Optimal Edge Fault-Tolerant Spanners

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6361312)