Sparse Spanners vs. Compact Routing

Cyril Gavoille and Christian Sommer
SPAA 2011 - 23rd ACM Symposium on Parallelism in Algorithms and Architectures (pp. 225-234)

Routing with multiplicative stretch 3 (which means that the path used by the routing scheme can be up to three times longer than a shortest path) can be done with routing tables of $$\widetilde{\Theta}(n^{1/2})$$ bits per node. The space lower bound is due to the existence of dense graphs with large girth. Dense graphs can be sparsified to subgraphs, called spanners, with various stretch guarantees. There are spanners with additive stretch guarantees (some even have constant additive stretch) but only very few additive routing schemes are known.

In this paper, we give reasons why routing in unweighted graphs with additive stretch is difficult in the form of space lower bounds for general graphs and for planar graphs. We prove that any routing scheme with additive stretch $$\beta$$ and addresses of poly-logarithmic length must use routing tables of size $$\widetilde{\Omega}\left(\frac{n}{\beta^2}\right)$$ bits per node for general graphs, and $$\widetilde{\Omega}\left(\frac{\sqrt{n}}{\beta}\right)$$ for planar graphs. Routing with tables of size $$O(n^{1/3})$$ thus requires a polynomial additive stretch of $$\widetilde{\Omega}(n^{1/3})$$, whereas spanners with average degree $$O(n^{1/3})$$ and constant additive stretch exist for all graphs. Spanners, however sparse they are, do not tell us how to route. These bounds provide the first separation of sparse spanner problems and compact routing problems.

On the positive side, we give an almost tight upper bound: we present the first non-trivial compact routing scheme with $$o(\log^2 n)$$-bit addresses, additive stretch $$\widetilde{O}(n^{1/3})$$, and table size $$\widetilde{O}(n^{1/3})$$ bits for all graphs with linear local tree-width such as planar, bounded-genus, and apex-minor-free graphs.

Note: Asymptotic notation in this abstract suppresses factors logarithmic in $$n$$.

@inproceedings{GS11,
author    = {Cyril Gavoille and Christian Sommer},
title     = {Sparse Spanners vs. Compact Routing},
booktitle = {23rd ACM Symposium on Parallelism
in Algorithms and Architectures (SPAA)},
year      = {2011},
pages     = {225--234},
url       = {http://dx.doi.org/10.1145/1989493.1989526},
doi       = {10.1145/1989493.1989526},
}


Official version
Local version (300.7 KB)
Slides (370.2 KB)

HomePublications → Sparse Spanners vs. Compact Routing