Multipath Spanners via Fault-Tolerant Spanners

摘要

An s-spanner H of a graph G is a subgraph such that the distance between any two vertices u and v in H is greater by at most a multiplicative factor s than the distance in G. In this paper, we focus on an extension of the concept of spanners to p-multipath distance, defined as the smallest length of a collection of p pairwise (vertex or edge) disjoint paths. The notion of multipath spanners was introduced in [15, 16] for edge (respectively, vertex) disjoint paths. This paper significantly improves the stretch-size tradeoff result of the two previous papers, using the related concept of fault-tolerant s-spanners, introduced in [6] for general graphs. More precisely, we show that at the cost of increasing the number of edges by a polynomial factor in p and s, it is possible to obtain an s-multipath spanner, thereby improving on the large stretch obtained in [15, 16].