Skip to Main content Skip to Navigation
Conference papers

Hardness of Exact Distance Queries in Sparse Graphs Through Hub Labeling

Adrian Kosowski 1 Przemysław Uznański 2 Laurent Viennot 1
1 GANG - Networks, Graphs and Algorithms
IRIF (UMR_8243) - Institut de Recherche en Informatique Fondamentale, Inria de Paris
Abstract : A distance labeling scheme is an assignment of bit-labels to the vertices of an undirected, unweighted graph such that the distance between any pair of vertices can be decoded solely from their labels. An important class of distance labeling schemes is that of hub labelings, where a node $v \in G$ stores its distance to the so-called hubs $S_v \subseteq V$, chosen so that for any $u,v \in V$ there is $w \in S_u \cap S_v$ belonging to some shortest $uv$ path. Notice that for most existing graph classes, the best distance labelling constructions existing use at some point a hub labeling scheme at least as a key building block. Our interest lies in hub labelings of sparse graphs, i.e., those with $|E(G)| = O(n)$, for which we show a lowerbound of $\frac{n}{2^{O(\sqrt{\log n})}}$ for the average size of the hubsets. Additionally, we show a hub-labeling construction for sparse graphs of average size $O(\frac{n}{RS(n)^{c}})$ for some $0 < c < 1$, where $RS(n)$ is the so-called Ruzsa-Szemer{\'e}di function, linked to structure of induced matchings in dense graphs. This implies that further improving the lower bound on hub labeling size to $\frac{n}{2^{(\log n)^{o(1)}}}$ would require a breakthrough in the study of lower bounds on $RS(n)$, which have resisted substantial improvement in the last 70 years. For general distance labeling of sparse graphs, we show a lowerbound of $\frac{1}{2^{O(\sqrt{\log n})}} SumIndex(n)$, where $SumIndex(n)$ is the communication complexity of the Sum-Index problem over $Z_n$. Our results suggest that the best achievable hub-label size and distance-label size in sparse graphs may be $\Theta(\frac{n}{2^{(\log n)^c}})$ for some $0
Document type :
Conference papers
Complete list of metadatas
Contributor : Adrian Kosowski <>
Submitted on : Tuesday, January 7, 2020 - 12:34:39 AM
Last modification on : Friday, April 10, 2020 - 5:30:42 PM

Links full text




Adrian Kosowski, Przemysław Uznański, Laurent Viennot. Hardness of Exact Distance Queries in Sparse Graphs Through Hub Labeling. PODC '19 - ACM Symposium on Principles of Distributed Computing, 2019, Toronto, Canada. pp.272-279, ⟨10.1145/3293611.3331625⟩. ⟨hal-02429930⟩



Record views