Sparse Spanners vs. Compact Routing

摘要

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 Θ(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 using routing tables of size μ bits per node and addresses of poly-logarithmic length has additive stretch Ω( (n/μ)~(1/2)) for general graphs, and Ω( (n/μ)~(1/2)) for planar graphs, respectively. Routing with tables of size O(n~(1/3)) thus requires a polynomial additive stretch of Ω(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(lg~2n)-bit addresses, additive stretch O(n~(1/3) ), and table size O(n~(1/3)) bits for all graphs with linear local tree-width such as planar, bounded-genus, and apex-minor-free graphs.