Sometimes Reliable Spanners of Almost Linear Size
share
Reliable spanners can withstand huge failures, even when a linear number of vertices are deleted from the network. In case of failures, a reliable spanner may have some additional vertices for which the spanner property no longer holds, but this collateral damage is bounded by a fraction of the size of the attack. It is known that Ω(nlog n) edges are needed to achieve this strong property, where n is the number of vertices in the network, even in one dimension. Constructions of reliable geometric (1+ε)-spanners, for n points in ^d, are known, where the resulting graph has O( n log n loglog^6n ) edges. Here, we show randomized constructions of smaller size spanners that have the desired reliability property in expectation or with good probability. The new construction is simple, and potentially practical – replacing a hierarchical usage of expanders (which renders the previous constructions impractical) by a simple skip-list like construction. This results in a 1-spanner, on the line, that has linear number of edges. Using this, we present a construction of a reliable spanner in ^d with O( n loglog^2 n logloglog n ) edges.
READ FULL TEXT