Hardness of Exact Distance Queries in Sparse Graphs Through Hub Labeling - Archive ouverte HAL Access content directly
Conference Papers Year : 2019

Hardness of Exact Distance Queries in Sparse Graphs Through Hub Labeling

(1) , (2) , (1)
1
2
Adrian Kosowski
  • Function : Author
  • PersonId : 1025291
Przemysław Uznański
  • Function : Author
  • PersonId : 1057030
Laurent Viennot

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

Dates and versions

hal-02429930 , version 1 (07-01-2020)

Identifiers

Cite

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⟩
22 View
0 Download

Altmetric

Share

Gmail Facebook Twitter LinkedIn More