Multipath Spanners

This paper concerns graph spanners that approximate multipaths between pair of vertices of an undirected graphs with

n

vertices. Classically, a spanner

H

of stretch

s

for a graph

G

is a spanning subgraph such that the distance in

H

between any two vertices is at most

s

times the distance in

G

. We study in this paper spanners that approximate short cycles, and more generally

p

edge-disjoint paths with

p

 > 1, between any pair of vertices.

For every unweighted graph

G

, we construct a 2-multipath 3-spanner of

O

(

n

3/2

) edges. In other words, for any two vertices

u

,

v

of

G

, the length of the shortest cycle (with no edge replication) traversing

u

,

v

in the spanner is at most thrice the length of the shortest one in

G

. This construction is shown to be optimal in term of stretch and of size. In a second construction, we produce a 2-multipath (2,8)-spanner of

O

(

n

3/2

) edges, i.e., the length of the shortest cycle traversing any two vertices have length at most twice the shortest length in

G

plus eight. For arbitrary

p

, we observe that, for each integer

k

 ≥ 1, every weighted graph has a

p

-multipath

p

(2

k

 − 1)-spanner with

O

(

p

n

1 + 1/

k

) edges, leaving open the question whether, with similar size, the stretch of the spanner can be reduced to 2

k

 − 1 for all

p

 > 1.