Document Open Access Logo

On the Complexity of the (Approximate) Nearest Colored Node Problem

Author Maximilian Probst

PDF
Thumbnail PDF

File

LIPIcs.ESA.2018.68.pdf
  • Filesize: 0.61 MB
  • 14 pages

Document Identifiers

Author Details

Maximilian Probst
  • BARC, University of Copenhagen, Universitetsparken 5, Copenhagen 2100, Denmark

Funding

Supported by Basic Algorithms Research Copenhagen (BARC), supported by Thorup’s Investigator Grant from the Villum Foundation under Grant No. 16582.

Cite AsGet BibTex

Maximilian Probst. On the Complexity of the (Approximate) Nearest Colored Node Problem. In 26th Annual European Symposium on Algorithms (ESA 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 112, pp. 68:1-68:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
https://doi.org/10.4230/LIPIcs.ESA.2018.68

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 Vertex-label Distance Oracle) of stretch 4k-5 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 color-reassignments. 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.

Subject Classification

ACM Subject Classification
  • Theory of computation → Design and analysis of algorithms
  • Theory of computation → Graph algorithms analysis
  • Theory of computation → Cell probe models and lower bounds
Keywords
  • Nearest Colored Node
  • Distance Oracles
  • Cell-probe lower bounds

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

Related Versions

References

  1. Amir Abboud and Virginia Vassilevska Williams. Popular conjectures imply strong lower bounds for dynamic problems. In Foundations of Computer Science (FOCS), 2014 IEEE 55th Annual Symposium on, pages 434-443. IEEE, 2014. Google Scholar
  2. Ittai Abraham, Shiri Chechik, Michael Elkin, Arnold Filtser, and Ofer Neiman. Ramsey spanning trees and their applications. In Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 1650-1664. SIAM, 2018. Google Scholar
  3. Yair Bartal, Nathan Linial, Manor Mendel, and Assaf Naor. On metric ramsey-type phenomena. In Proceedings of the Thirty-fifth Annual ACM Symposium on Theory of Computing, STOC '03, pages 463-472, New York, NY, USA, 2003. ACM. URL: http://dx.doi.org/10.1145/780542.780610.
  4. Djamal Belazzougui and Gonzalo Navarro. Optimal lower and upper bounds for representing sequences. ACM Trans. Algorithms, 11(4):31:1-31:21, 2015. URL: http://dx.doi.org/10.1145/2629339.
  5. Michael A. Bender and Martin Farach-Colton. The lca problem revisited. In Proceedings of the 4th Latin American Symposium on Theoretical Informatics, LATIN '00, pages 88-94, London, UK, UK, 2000. Springer-Verlag. URL: http://dl.acm.org/citation.cfm?id=646388.690192.
  6. Shiri Chechik. Improved distance oracles and spanners for vertex-labeled graphs. In Proceedings of the 20th Annual European Conference on Algorithms, ESA'12, pages 325-336, Berlin, Heidelberg, 2012. Springer-Verlag. URL: http://dx.doi.org/10.1007/978-3-642-33090-2_29.
  7. Shiri Chechik. Approximate distance oracles with constant query time. In Proceedings of the forty-sixth annual ACM symposium on Theory of computing, pages 654-663. ACM, 2014. Google Scholar
  8. Shiri Chechik. Approximate distance oracles with improved bounds. In Proceedings of the Forty-Seventh Annual ACM on Symposium on Theory of Computing, pages 1-10. ACM, 2015. Google Scholar
  9. Martin Dietzfelbinger, Anna Karlin, Kurt Mehlhorn, Friedhelm Meyer auF der Heide, Hans Rohnert, and Robert E Tarjan. Dynamic perfect hashing: Upper and lower bounds. SIAM Journal on Computing, 23(4):738-761, 1994. Google Scholar
  10. Johannes Fischer and Volker Heun. Theoretical and Practical Improvements on the RMQ-Problem, with Applications to LCA and LCE, pages 36-48. Springer Berlin Heidelberg, Berlin, Heidelberg, 2006. URL: http://dx.doi.org/10.1007/11780441_5.
  11. Pawel Gawrychowski, Gad M Landau, Shay Mozes, and Oren Weimann. The nearest colored node in a tree. In LIPIcs-Leibniz International Proceedings in Informatics, volume 54. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, 2016. Google Scholar
  12. Monika Henzinger, Sebastian Krinninger, Danupon Nanongkai, and Thatchaphol Saranurak. Unifying and strengthening hardness for dynamic problems via the online matrix-vector multiplication conjecture. In Proceedings of the forty-seventh annual ACM symposium on Theory of computing, pages 21-30. ACM, 2015. Google Scholar
  13. Danny Hermelin, Avivit Levy, Oren Weimann, and Raphael Yuster. Distance Oracles for Vertex-Labeled Graphs, pages 490-501. Springer Berlin Heidelberg, Berlin, Heidelberg, 2011. URL: http://dx.doi.org/10.1007/978-3-642-22012-8_39.
  14. Itay Laish and Shay Mozes. Efficient approximate distance oracles for vertex-labeled planar graphs. arXiv preprint arXiv:1707.02414, 2017. Google Scholar
  15. Manor Mendel and Assaf Naor. Ramsey partitions and proximity data structures. In Foundations of Computer Science, 2006. FOCS'06. 47th Annual IEEE Symposium on, pages 109-118. IEEE, 2006. Google Scholar
  16. Shay Mozes and Eyal E Skop. Efficient vertex-label distance oracles for planar graphs. Theory of Computing Systems, 62(2):419-440, 2018. Google Scholar
  17. Mihai Pǎtraşcu. Towards polynomial lower bounds for dynamic problems. In Proc. 42nd ACM Symposium on Theory of Computing (STOC), pages 603-610, 2010. Google Scholar
  18. Mihai Pătraşcu and Mikkel Thorup. Time-space trade-offs for predecessor search. In Proceedings of the thirty-eighth annual ACM symposium on Theory of computing, pages 232-240. ACM, 2006. Google Scholar
  19. Mihai Pǎtraşcu and Mikkel Thorup. Randomization does not help searching predecessors. In Proceedings of the eighteenth annual ACM-SIAM symposium on Discrete algorithms, pages 555-564. Society for Industrial and Applied Mathematics, 2007. Google Scholar
  20. Liam Roditty, Mikkel Thorup, and Uri Zwick. Deterministic constructions of approximate distance oracles and spanners. In International Colloquium on Automata, Languages, and Programming, pages 261-272. Springer, 2005. Google Scholar
  21. Mikkel Thorup and Uri Zwick. Compact routing schemes. In Proceedings of the Thirteenth Annual ACM Symposium on Parallel Algorithms and Architectures, SPAA '01, pages 1-10, New York, NY, USA, 2001. ACM. URL: http://dx.doi.org/10.1145/378580.378581.
  22. Mikkel Thorup and Uri Zwick. Approximate distance oracles. J. ACM, 52(1):1-24, 2005. URL: http://dx.doi.org/10.1145/1044731.1044732.
  23. Dekel Tsur. Succinct data structures for nearest colored node in a tree. Information Processing Letters, 132:6-10, 2018. Google Scholar
  24. Virginia Vassilevska Williams and Ryan Williams. Subcubic equivalences between path, matrix and triangle problems. In Foundations of Computer Science (FOCS), 2010 51st Annual IEEE Symposium on, pages 645-654. IEEE, 2010. Google Scholar
  25. Christian Wulff-Nilsen. Approximate distance oracles with improved query time. In Proceedings of the twenty-fourth annual ACM-SIAM symposium on Discrete algorithms, pages 539-549. SIAM, 2013. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact