Multipath Spanners

1 LaBRI - Laboratoire Bordelais de Recherche en Informatique 2 CEPAGE - Algorithmics for computationally intensive applications over wide scale distributed platforms Université Sciences et Technologies - Bordeaux 1, Inria Bordeaux - Sud-Ouest, École Nationale Supérieure d-Électronique, Informatique et Radiocommunications de Bordeaux ENSEIRB, CNRS - Centre National de la Recherche Scientifique : UMR5800 3 IUF - Institut Universitaire de France 4 LIAFA - Laboratoire d-informatique Algorithmique : Fondements et Applications 5 GANG - Networks, Graphs and Algorithms LIAFA - Laboratoire d-informatique Algorithmique : Fondements et Applications, Inria Paris-Rocquencourt

Abstract : 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 \$On^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 \$On^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\ge 1\$, every weighted graph has a \$p\$-multipath \$p2k-1\$-spanner with \$Op n^1+1-k\$ edges, leaving open the question whether, with similar size, the stretch of the spanner can be reduced to \$2k-1\$ for all \$p>1\$.

Author: Cyril Gavoille - Quentin Godfroy - Laurent Viennot -

Source: https://hal.archives-ouvertes.fr/