Fault-Tolerant Spanners against Bounded-Degree Edge Failures: Linearly More Faults, Almost For Free

We study a new and stronger notion of fault-tolerant graph structures whose size bounds depend on the degree of the failing edge set, rather than the total number of faults. For a subset of faulty edges F ⊆ G, the faulty-degree deg(F ) is the largest number of faults in F incident to any given vertex. For example, a matching F has deg(F ) = 1 while |F | might be as large as n/2.

We design new fault-tolerant structures with size comparable to previous constructions, but which tolerate every fault set of small faulty-degree deg(F ), rather than only fault sets of small size |F |. Thus, for example, our structures can tolerate a linear number of edge faults with almost the same size bounds currently known for handling a single edge failure, provided that the edge faults are arranged in a matching. Our main results are: