Extremal Compactness

Because Interval Routing is devoted to implement routing in general networks, it is natural to wonder what is the compactness of an n-node graph.

The compactness of an n-node graph cannot exceed n/2, because a necessary condition to have k intervals for a set I is to have $\vert I\vert \leqs n-k$, and clearly the number of intervals of I is at most |I|. The next result proposes a little improvement. The three next results use randomization.

Theorem 15 is actually a consequence of a deeper result: for every family $\cF$ of subsets of $\{1,\ldots,n\}$ containing at most e^n/2/n distinct subsets there exists a permutation $\pi$ of $\{1,\ldots,n\}$ such that all the subsets of $\cF$ are composed of at most $n/4+O(\sqrt{n\ln{n}})$ intervals under $\pi$. It can be clearly applied on IRS models where Condition 2a and/or 2b (disjunction of the arc-labels) are relaxed, $\cF$ representing the set of arcs, each subsets representing an arc-label, and the permutation $\pi$ representing the node-labeling.

Due to the next lower bound, n/4 is asymptotically a tight bound.

To a certain extent Interval Routing cannot be efficiently used for the t-regional routing problem posed by Peleg in [SRS97], that consists in optimal routing up to distance t (cf. Definition 7 in Paragraph 2.5).

Note that there exists a constructive proof for a worst-case compactness of at least n/12 [GG98]. A third proof, using randomization, for a $\Theta(n)$-lower bound is given in [KK96]. They also show that $\Theta(n)$ intervals might be required simultaneously on $\Theta(n)$ edges.

Against intuition, the next result shows that, in general, the compactness does not depend on the number of edges or on the maximum degree of the graph. It may be quite high even for sparse graphs.

As a corollary, there exists some graph with $(1+\varepsilon)n$ edges, for every $0 < \varepsilon \leqs 1/2$, and of compactness  $\Theta(\varepsilon n)$. Indeed, it suffices to choose a graph satisfying Theorem 17 with $2\varepsilon n$ nodes, and to connect $(1-2\varepsilon)n$ nodes of degree 1 to some nodes. Clearly such a new graph has n nodes, $3\varepsilon n + (1-2\varepsilon)n = (1+\varepsilon)n$ edges, and compactness  $\Theta(\varepsilon n)$.

A way to prove Theorem 17 is to use the result of [GP96b] about the memory requirement of a graph, which defines the smallest amount of memory needed to code any shortest path routing function (see [FG97] for an introduction to Universal Routing Schemes). In [GP96b] n-node graphs of degree bounded by d, $3 \leqs d \leqs \varepsilon n$ for $\varepsilon < 1$, of local memory requirement $\Theta(n\log{d})$ are constructed. This result, combined with Theorem 1, implies Theorem 17 (for d = 3 with a slightly modification to have a 3-regular graph).

We have also the following isolated results to quickly check whether a graph has compactness 1: