Document Open Access Logo

Covering Metric Spaces by Few Trees

Authors Yair Bartal, Nova Fandina, Ofer Neiman

PDF
Thumbnail PDF

File

LIPIcs.ICALP.2019.20.pdf
  • Filesize: 0.52 MB
  • 16 pages

Document Identifiers

Author Details

Yair Bartal
  • Department of Computer Science, Hebrew University of Jerusalem, Israel
Nova Fandina
  • Department of Computer Science, Hebrew University of Jerusalem, Israel
Ofer Neiman
  • Department of Computer Science, Ben-Gurion University of the Negev, Beer-Sheva, Israel

Funding

  • Bartal, Yair: Supported in part by a grant from the Israeli Science Foundation (1817/17).
  • Fandina, Nova: Supported in part by a grant from the Israeli Science Foundation (1817/17).
  • Neiman, Ofer: Supported in part by a grant from the Israeli Science Foundation (1817/17) and in part by BSF grant 2015813.

Acknowledgements

We are grateful to Michael Elkin and Shay Solomon for fruitful discussions.

Cite AsGet BibTex

Yair Bartal, Nova Fandina, and Ofer Neiman. Covering Metric Spaces by Few Trees. In 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 132, pp. 20:1-20:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
https://doi.org/10.4230/LIPIcs.ICALP.2019.20

Abstract

A tree cover of a metric space (X,d) is a collection of trees, so that every pair x,y in X has a low distortion path in one of the trees. If it has the stronger property that every point x in X has a single tree with low distortion paths to all other points, we call this a Ramsey tree cover. Tree covers and Ramsey tree covers have been studied by [Yair Bartal et al., 2005; Anupam Gupta et al., 2004; T-H. Hubert Chan et al., 2005; Gupta et al., 2006; Mendel and Naor, 2007], and have found several important algorithmic applications, e.g. routing and distance oracles. The union of trees in a tree cover also serves as a special type of spanner, that can be decomposed into a few trees with low distortion paths contained in a single tree; Such spanners for Euclidean pointsets were presented by [S. Arya et al., 1995]. In this paper we devise efficient algorithms to construct tree covers and Ramsey tree covers for general, planar and doubling metrics. We pay particular attention to the desirable case of distortion close to 1, and study what can be achieved when the number of trees is small. In particular, our work shows a large separation between what can be achieved by tree covers vs. Ramsey tree covers.

Subject Classification

ACM Subject Classification
  • Mathematics of computing → Graph algorithms
  • Theory of computation → Sparsification and spanners
Keywords
  • tree cover
  • Ramsey tree cover
  • probabilistic hierarchical family

Metrics

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

Related Versions

References

  1. Ittai Abraham, Yair Bartal, and Ofer Neiman. Advances in metric embedding theory. Advances in Mathematics, 228(6):3026-3126, 2011. URL: http://dx.doi.org/10.1016/j.aim.2011.08.003.
  2. Ittai Abraham, Yair Bartal, and Ofer Neiman. Embedding Metrics into Ultrametrics and Graphs into Spanning Trees with Constant Average Distortion. SIAM J. Comput., 44(1):160-192, 2015. URL: http://dx.doi.org/10.1137/120884390.
  3. 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, SODA 2018, New Orleans, LA, USA, January 7-10, 2018, pages 1650-1664, 2018. URL: http://dx.doi.org/10.1137/1.9781611975031.108.
  4. Ittai Abraham and Cyril Gavoille. Object location using path separators. In Proceedings of the Twenty-Fifth Annual ACM Symposium on Principles of Distributed Computing, PODC 2006, Denver, CO, USA, July 23-26, 2006, pages 188-197, 2006. URL: http://dx.doi.org/10.1145/1146381.1146411.
  5. Ittai Abraham and Ofer Neiman. Using petal-decompositions to build a low stretch spanning tree. In Proceedings of the 44th Symposium on Theory of Computing Conference, STOC 2012, New York, NY, USA, May 19 - 22, 2012, pages 395-406, 2012. URL: http://dx.doi.org/10.1145/2213977.2214015.
  6. Noga Alon, Richard M. Karp, David Peleg, and Douglas West. A Graph-Theoretic Game and its Application to the k-Server Problem. SIAM J. Comput., 24(1):78-100, 1995. Google Scholar
  7. Ingo Althöfer, Gautam Das, David Dobkin, and Deborah Joseph. Generating sparse spanners for weighted graphs. In John R. Gilbert and Rolf Karlsson, editors, SWAT 90, pages 26-37, Berlin, Heidelberg, 1990. Springer Berlin Heidelberg. Google Scholar
  8. S. Arya, G. Das, D. M. Mount, J. S. Salowe, and M. H. M. Smid. Euclidean spanners: short, thin, and lanky. In Proc. of 27th STOC, pages 489-498, 1995. Google Scholar
  9. Baruch Awerbuch. Complexity of network synchronization. J. ACM, 32(4):804-823, October 1985. URL: http://dx.doi.org/10.1145/4221.4227.
  10. Baruch Awerbuch, Bonnie Berger, Lenore Cowen, and David Peleg. Near-Linear Cost Sequential and Distribured Constructions of Sparse Neighborhood Covers. In 34th Annual Symposium on Foundations of Computer Science, Palo Alto, California, USA, 3-5 November 1993, pages 638-647, 1993. URL: http://dx.doi.org/10.1109/SFCS.1993.366823.
  11. Yair Bartal. Probabilistic Approximations of Metric Spaces and Its Algorithmic Applications. In 37th Annual Symposium on Foundations of Computer Science, FOCS '96, Burlington, Vermont, USA, 14-16 October, 1996, pages 184-193, 1996. Google Scholar
  12. Yair Bartal. On Approximating Arbitrary Metrices by Tree Metrics. In Proceedings of the Thirtieth Annual ACM Symposium on the Theory of Computing, Dallas, Texas, USA, May 23-26, 1998, pages 161-168, 1998. URL: http://dx.doi.org/10.1145/276698.276725.
  13. Yair Bartal. Graph Decomposition Lemmas and their Role in Metric Embedding Methods. In 12th Annual European Symposium on Algorithms, pages 89-97, 2004. URL: http://springerlink.metapress.com/openurl.asp?genre=article&issn=0302-9743&volume=3221&spage=89.
  14. Yair Bartal. Lecture notes. In Metric embedding theory and its algorithmic applications course, 2011. URL: http://moodle.cs.huji.ac.il/cs10/file.php/67720/GM_Lecture6.pdf.
  15. Yair Bartal, Nathan Linial, Manor Mendel, and Assaf Naor. On metric ramsey-type phenomena. Annals Math, 162(2):643-709, 2005. Google Scholar
  16. S. Baswana and S. Sen. A Simple Linear Time algorithm for Computing a (2k-1)-Spanner of O(n^1+1/k) Size in Weighted Graphs. In Proceedings of the 30th International Colloquium on Automata, Languages and Programming, volume 2719 of LNCS, pages 384-396. Springer, 2003. Google Scholar
  17. Guy E. Blelloch, Yan Gu, and Yihan Sun. A New Efficient Construction on Probabilistic Tree Embeddings. CoRR, abs/1605.04651, 2016. URL: http://arxiv.org/abs/1605.04651.
  18. Béla Bollobas. Extremal Graph Theory. Dover Publications, Inc., New York, NY, USA, 2004. Google Scholar
  19. T-H. Hubert Chan, Anupam Gupta, Bruce M. Maggs, and Shuheng Zhou. On Hierarchical routing in Doubling Metrics. In Proc. 16th Ann. ACM-SIAM Symposium on Discrete Algorithms (SODA), 2005. Google Scholar
  20. B. Chandra, G. Das, G. Narasimhan, and J. Soares. New sparseness results on graph spanners. Int. J. Comput. Geometry Appl., 5:125-144, 1995. Google Scholar
  21. Moses Charikar, Chandra Chekuri, Ashish Goel, Sudipto Guha, and Serge Plotkin. Approximating a Finite Metric by a Small Number of Tree Metrics. In FOCS '98: Proceedings of the 39th Annual Symposium on Foundations of Computer Science, page 379, Washington, DC, USA, 1998. IEEE Computer Society. Google Scholar
  22. Edith Cohen. Fast algorithms for constructing t-spanners and paths with stretch t. In 34th Annual Symposium on Foundations of Computer Science, Palo Alto, California, USA, 3-5 November 1993, pages 648-658, 1993. URL: http://dx.doi.org/10.1109/SFCS.1993.366822.
  23. Michael Elkin, Yuval Emek, Daniel A. Spielman, and Shang-Hua Teng. Lower-stretch spanning trees. In STOC '05: Proceedings of the thirty-seventh annual ACM symposium on Theory of computing, pages 494-503, New York, NY, USA, 2005. ACM Press. URL: http://dx.doi.org/10.1145/1060590.1060665.
  24. Michael Elkin and David Peleg. (1+epsilon, beta)-Spanner Constructions for General Graphs. SIAM J. Comput., 33(3):608-631, 2004. URL: http://dx.doi.org/10.1137/S0097539701393384.
  25. Michael Elkin and Seth Pettie. A Linear-Size Logarithmic Stretch Path-Reporting Distance Oracle for General Graphs. In Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2015, San Diego, CA, USA, January 4-6, 2015, pages 805-821, 2015. URL: http://dx.doi.org/10.1137/1.9781611973730.55.
  26. P. Erdős and L. Lovász. Problems and results on 3-chromatic hypergraphs and some related questions. Infinite and finite sets, 10(2):609-–627, 1975. Google Scholar
  27. Jittat Fakcharoenphol, Satish Rao, and Kunal Talwar. A tight bound on approximating arbitrary metrics by tree metrics. J. Comput. Syst. Sci., 69(3):485-497, November 2004. URL: http://dx.doi.org/10.1016/j.jcss.2004.04.011.
  28. Arnold Filtser and Ofer Neiman. Light Spanners for High Dimensional Norms via Stochastic Decompositions. In 26th Annual European Symposium on Algorithms, 2018. Google Scholar
  29. Jie Gao, Leonidas J. Guibas, and An Nguyen. Deformable Spanners and Applications. In Proceedings of the Twentieth Annual Symposium on Computational Geometry, SCG '04, pages 190-199, New York, NY, USA, 2004. ACM. URL: http://dx.doi.org/10.1145/997817.997848.
  30. Anupam Gupta, Mohammad T. Hajiaghayi, and Harald Räcke. Oblivious Network Design. In Proceedings of the Seventeenth Annual ACM-SIAM Symposium on Discrete Algorithm, SODA '06, pages 970-979, Philadelphia, PA, USA, 2006. Society for Industrial and Applied Mathematics. URL: http://dl.acm.org/citation.cfm?id=1109557.1109665.
  31. Anupam Gupta, Amit Kumar, and Rajeev Rastogi. Traveling with a Pez Dispenser (or, Routing Issues in MPLS). SIAM J. Comput., 34(2):453-474, 2004. URL: http://dx.doi.org/10.1137/S0097539702409927.
  32. Sariel Har-Peled and Manor Mendel. Fast Construction of Nets in Low-Dimensional Metrics and Their Applications. SIAM J. Comput, 35(5):1148-1184, 2006. Google Scholar
  33. Philip Klein, Serge A. Plotkin, and Satish Rao. Excluded minors, network decomposition, and multicommodity flow. In Proceedings of the twenty-fifth annual ACM symposium on Theory of computing, STOC '93, pages 682-690, New York, NY, USA, 1993. ACM. URL: http://dx.doi.org/10.1145/167088.167261.
  34. Philip N. Klein. Preprocessing an undirected planar network to enable fast approximate distance queries. In Proceedings of the Thirteenth Annual ACM-SIAM Symposium on Discrete Algorithms, January 6-8, 2002, San Francisco, CA, USA., pages 820-827, 2002. URL: http://dl.acm.org/citation.cfm?id=545381.545488.
  35. Robert Krauthgamer, James R. Lee, Manor Mendel, and Assaf Naor. Measured descent: A new embedding method for finite metrics. In 45th Annual IEEE Symposium on Foundations of Computer Science, pages 434-443. IEEE, October 2004. Google Scholar
  36. Nathan Linial and Michael Saks. Decomposing graphs into regions of small diameter. In SODA '91: Proceedings of the second annual ACM-SIAM symposium on Discrete algorithms, pages 320-330, Philadelphia, PA, USA, 1991. Society for Industrial and Applied Mathematics. Google Scholar
  37. Richard J. Lipton and Robert Endre Tarjan. Applications of a Planar Separator Theorem. SIAM J. Comput., 9(3):615-627, 1980. URL: http://dx.doi.org/10.1137/0209046.
  38. Manor Mendel and Assaf Naor. Ramsey partitions and proximity data structures. Journal of the European Mathematical Society, 9(2):253-275, 2007. Google Scholar
  39. Robin A. Moser and Gábor Tardos. A constructive proof of the general Lovasz Local Lemma. CoRR, abs/0903.0544, 2009. URL: http://arxiv.org/abs/0903.0544.
  40. Assaf Naor and Terence Tao. Scale-oblivious metric fragmentation and the nonlinear Dvoretzky theorem. Israel Journal of Mathematics, 192(1):489-504, 2012. URL: http://dx.doi.org/10.1007/s11856-012-0039-7.
  41. G. Narasimhan and M. Smid. Geometric Spanner Networks. Cambridge University Press, 2007. Google Scholar
  42. D. Peleg and A. Schäffer. Graph Spanners. J. Graph Theory, 13:99-116, 1989. Google Scholar
  43. D. Peleg and E. Upfal. A tradeoff between size and efficiency for routing tables. J. of the ACM, 36:510-530, 1989. Google Scholar
  44. Yuri Rabinovich and Ran Raz. Lower Bounds on the Distortion of Embedding Finite Metric Spaces in Graphs. Discrete & Computational Geometry, 19(1):79-94, 1998. URL: http://link.springer.de/link/service/journals/00454/bibs/19n1p79.html.
  45. Satish Rao and Warren D. Smith. Approximating Geometrical Graphs via "Spanners" and "Banyans". In Proceedings of the Thirtieth Annual ACM Symposium on the Theory of Computing, Dallas, Texas, USA, May 23-26, 1998, pages 540-550, 1998. URL: http://dx.doi.org/10.1145/276698.276868.
  46. M. Thorup and U. Zwick. Approximate Distance Oracles. In 33^rd Annual ACM Symposium on Theory of Computing (STOC), pages 183-192, Hersonissos, Crete, Greece, July 2001. Google Scholar
  47. M. Thorup and U. Zwick. Spanners and emulators with sublinear distance errors. In Proc. of Symp. on Discr. Algorithms, pages 802-809, 2006. Google Scholar
  48. Mikkel Thorup. Compact oracles for reachability and approximate distances in planar digraphs. J. ACM, 51(6):993-1024, 2004. URL: http://dx.doi.org/10.1145/1039488.1039493.
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