Sparse Spanners vs. Compact Routing
Résumé
Routing with \emph{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 $\tTheta(\sqrt{n}\,)$~bits\footnote{Tilde-big-$O$ notation is similar to big-$O$ notation up to factors poly-logarithmic in $n$.} 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 \emph{spanners}, with various stretch guarantees. There are spanners with \emph{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 \emph{additive} stretch is difficult in the form of space lower bounds for general graphs and for planar graphs. We prove that any routing scheme using routing tables of size $\mem$~bits per node and addresses of poly-logarithmic length has additive stretch $\tOmega(\sqrt{n/\mem}\,)$ for general graphs, and $\tOmega(\sqrt{n}/\mem)$ for planar graphs, respectively. Routing with tables of size $\tO(n^{1/3})$ thus requires a polynomial additive stretch of $\tOmega(n^{1/3})$, whereas spanners with average degree $O(n^{1/3})$ and {\em 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(\lg^2 n)$-bit addresses, {\em additive} stretch $\tO(n^{1/3})$, and table size $\tO(n^{1/3})$~bits for all graphs with linear local tree-width such as planar, bounded-genus, and apex-minor-free graphs.