15 października 2019 10:15
[Seminarium ZOK] Przemysław Uznański o "Hardness of Exact Distance Queries in Sparse Graphs Through Hub Labeling" (PODC 2019, joint work with Adrian Kosowski and Laurent Viennot)
Tytuł: Hardness of Exact Distance Queries in Sparse Graphs Through Hub Labeling
Autorzy: Adrian Kosowski, Przemysław Uznański, Laurent Viennot
Prelegent: Przemysław Uznański
Czas i miejsce: wtorek, 15-go października 2019, 10:15, sala 310.
Streszczenie:
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∈G stores its distance to the so-called hubs S(v)⊆V, chosen so that for any u,v∈V there is w∈S(u)∩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 n/2^O(√logn) for the average size of the hubsets. Additionally, we show a hub-labeling construction for sparse graphs of average size O(n/RS(n)^c) for some 0<c<1, where RS(n) is the so-called Ruzsa-Szemerédi function, linked to structure of induced matchings in dense graphs. This implies that further improving the lower bound on hub labeling size to n/2^(logn)^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 1/2O(√logn) * 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 Θ(n/2^(logn)^c) for some 0<c<1.
Praca była prezentowana na PODC 2019