Probst, Maximilian
On the Complexity of the (Approximate) Nearest Colored Node Problem
Abstract
Given a graph G=(V,E) where each vertex is assigned a color from the set C={c_1, c_2, .., c_sigma}. In the (approximate) nearest colored node problem, we want to query, given v in V and c in C, for the (approximate) distance dist^(v, c) from v to the nearest node of color c. For any integer 1 <= k <= log n, we present a Color Distance Oracle (also often referred to as Vertexlabel Distance Oracle) of stretch 4k5 using space O(kn sigma^{1/k}) and query time O(log{k}). This improves the query time from O(k) to O(log{k}) over the best known Color Distance Oracle by Chechik [Chechik, 2012].
We then prove a lower bound in the cell probe model showing that even for unweighted undirected paths any static data structure that uses space S requires at least Omega (log (log{sigma} / log(S/n)+log log{n})) query time to give a distance estimate of stretch O(polylog(n)). This implies for the important case when sigma = Theta(n^{epsilon}) for some constant 0 < epsilon < 1, that our Color Distance Oracle has asymptotically optimal query time in regard to k, and that recent Color Distance Oracles for trees [Tsur, 2018] and planar graphs [Mozes and Skop, 2018] achieve asymptotically optimal query time in regard to n.
We also investigate the setting where the data structure additionally has to support colorreassignments. We present the first Color Distance Oracle that achieves query times matching our lower bound from the static setting for large stretch yielding an exponential improvement over the best known query time [Chechik, 2014]. Finally, we give new conditional lower bounds proving the hardness of answering queries if edge insertions and deletion are allowed that strictly improve over recent bounds in time and generality.
BibTeX  Entry
@InProceedings{probst:LIPIcs:2018:9531,
author = {Maximilian Probst},
title = {{On the Complexity of the (Approximate) Nearest Colored Node Problem}},
booktitle = {26th Annual European Symposium on Algorithms (ESA 2018)},
pages = {68:168:14},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959770811},
ISSN = {18688969},
year = {2018},
volume = {112},
editor = {Yossi Azar and Hannah Bast and Grzegorz Herman},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2018/9531},
URN = {urn:nbn:de:0030drops95313},
doi = {10.4230/LIPIcs.ESA.2018.68},
annote = {Keywords: Nearest Colored Node, Distance Oracles, Cellprobe lower bounds}
}
14.08.2018
Keywords: 

Nearest Colored Node, Distance Oracles, Cellprobe lower bounds 
Seminar: 

26th Annual European Symposium on Algorithms (ESA 2018)

Issue date: 

2018 
Date of publication: 

14.08.2018 