Document Open Access Logo

Local Computation Algorithms for Spanners

Authors Merav Parter, Ronitt Rubinfeld, Ali Vakilian, Anak Yodpinyanee

PDF
Thumbnail PDF

File

LIPIcs.ITCS.2019.58.pdf
  • Filesize: 1.22 MB
  • 21 pages

Document Identifiers

Author Details

Merav Parter
  • Weizmann IS, Rehovot, Israel
Ronitt Rubinfeld
  • CSAIL, MIT, Cambridge, MA, USA and TAU, Tel Aviv, Israel
Ali Vakilian
  • CSAIL, MIT, Cambridge, MA, USA
Anak Yodpinyanee
  • CSAIL, MIT, Cambridge, MA, USA

Funding

  • Parter, Merav: MP is supported by Minerva Foundation (124042) and ISF-2084/18.
  • Rubinfeld, Ronitt: RR is supported by the NSF grants CCF-1650733, CCF-1733808, IIS-1741137 and CCF-1740751.
  • Vakilian, Ali: AV is supported by the NSF grant CCF-1535851.
  • Yodpinyanee, Anak: AY is supported by the NSF grants CCF-1650733, CCF-1733808, IIS-1741137 and the DPST scholarship, Royal Thai Government.

Cite AsGet BibTex

Merav Parter, Ronitt Rubinfeld, Ali Vakilian, and Anak Yodpinyanee. Local Computation Algorithms for Spanners. In 10th Innovations in Theoretical Computer Science Conference (ITCS 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 124, pp. 58:1-58:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
https://doi.org/10.4230/LIPIcs.ITCS.2019.58

Abstract

A graph spanner is a fundamental graph structure that faithfully preserves the pairwise distances in the input graph up to a small multiplicative stretch. The common objective in the computation of spanners is to achieve the best-known existential size-stretch trade-off efficiently. Classical models and algorithmic analysis of graph spanners essentially assume that the algorithm can read the input graph, construct the desired spanner, and write the answer to the output tape. However, when considering massive graphs containing millions or even billions of nodes not only the input graph, but also the output spanner might be too large for a single processor to store. To tackle this challenge, we initiate the study of local computation algorithms (LCAs) for graph spanners in general graphs, where the algorithm should locally decide whether a given edge (u,v) in E belongs to the output (sparse) spanner or not. Such LCAs give the user the "illusion" that a specific sparse spanner for the graph is maintained, without ever fully computing it. We present several results for this setting, including: - For general n-vertex graphs and for parameter r in {2,3}, there exists an LCA for (2r-1)-spanners with O~(n^{1+1/r}) edges and sublinear probe complexity of O~(n^{1-1/2r}). These size/stretch trade-offs are best possible (up to polylogarithmic factors). - For every k >= 1 and n-vertex graph with maximum degree Delta, there exists an LCA for O(k^2) spanners with O~(n^{1+1/k}) edges, probe complexity of O~(Delta^4 n^{2/3}), and random seed of size polylog(n). This improves upon, and extends the work of [Lenzen-Levi, ICALP'18]. We also complement these constructions by providing a polynomial lower bound on the probe complexity of LCAs for graph spanners that holds even for the simpler task of computing a sparse connected subgraph with o(m) edges. To the best of our knowledge, our results on 3 and 5-spanners are the first LCAs with sublinear (in Delta) probe-complexity for Delta = n^{Omega(1)}.

Subject Classification

ACM Subject Classification
  • Theory of computation → Sparsification and spanners
  • Theory of computation → Sketching and sampling
Keywords
  • Local Computation Algorithms
  • Sub-linear Algorithms
  • Graph Spanners

Metrics

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

References

  1. Noga Alon, Ronitt Rubinfeld, Shai Vardi, and Ning Xie. Space-efficient local computation algorithms. In Proc. 23rd ACM-SIAM Sympos. Discrete Algs. (SODA), pages 1132-1139, 2012. Google Scholar
  2. Baruch Awerbuch and David Peleg. Network synchronization with polylogarithmic overhead. In Proc. 31st Annu. IEEE Sympos. Found. Comput. Sci. (FOCS), pages 514-522, 1990. Google Scholar
  3. Baruch Awerbuch and David Peleg. Routing with polynomial communication-space trade-off. SIAM J. Discrete Math., 5(2):151-162, 1992. Google Scholar
  4. Surender Baswana, Sumeet Khurana, and Soumojit Sarkar. Fully dynamic randomized algorithms for graph spanners. ACM Transactions on Algorithms (TALG), 8(4):35, 2012. Google Scholar
  5. Surender Baswana and Sandeep Sen. A Simple and Linear Time Randomized Algorithm for Computing Sparse Spanners in Weighted Graphs. Random Structures and Algorithms, 30(4):532-563, 2007. Google Scholar
  6. Greg Bodwin and Sebastian Krinninger. Fully Dynamic Spanners with Worst-Case Update Time. In Proc. 24th Annu. European Sympos. Algorithms (ESA), pages 17:1-17:18, 2016. Google Scholar
  7. Keren Censor-Hillel, Merav Parter, and Gregory Schwartzman. Derandomizing Local Distributed Algorithms under Bandwidth Restrictions. In 31st International Symposium on Distributed Computing, DISC 2017, October 16-20, 2017, Vienna, Austria, pages 11:1-11:16, 2017. Google Scholar
  8. Bilel Derbel and Cyril Gavoille. Fast deterministic distributed algorithms for sparse spanners. Theoretical Computer Science, 2008. Google Scholar
  9. Bilel Derbel, Cyril Gavoille, and David Peleg. Deterministic distributed construction of linear stretch spanners in polylogarithmic time. In Proc. 21st Int. Symp. Dist. Comp. (DISC), pages 179-192, 2007. Google Scholar
  10. Bilel Derbel, Cyril Gavoille, David Peleg, and Laurent Viennot. On the locality of distributed sparse spanner construction. In Proceedings of the Twenty-Seventh Annual ACM Symposium on Principles of Distributed Computing, PODC 2008, Toronto, Canada, August 18-21, 2008, pages 273-282, 2008. Google Scholar
  11. Bilel Derbel, Cyril Gavoille, David Peleg, and Laurent Viennot. Local computation of nearly additive spanners. In Proc. 23rd Int. Symp. Dist. Comp. (DISC), 2009. Google Scholar
  12. Michael Elkin. Streaming and fully dynamic centralized algorithms for constructing and maintaining sparse spanners. ACM Transactions on Algorithms (TALG), 7(2):20, 2011. Google Scholar
  13. Michael Elkin and Ofer Neiman. Efficient Algorithms for Constructing Very Sparse Spanners and Emulators. In Proc. 28th ACM-SIAM Sympos. Discrete Algs. (SODA), pages 652-669, 2017. Google Scholar
  14. P Erdös. On some extremal problems in graph theory. Israel Journal of Mathematics, 3(2):113-116, 1965. Google Scholar
  15. Guy Even, Moti Medina, and Dana Ron. Deterministic stateless centralized local algorithms for bounded degree graphs. In Proc. 22nd Annu. European Sympos. Algorithms (ESA), pages 394-405, 2014. Google Scholar
  16. Mohsen Ghaffari and Jara Uitto. Sparsifying distributed algorithms with ramifications in massively parallel computation and centralized local computation. Proc. 30th ACM-SIAM Sympos. Discrete Algs. (SODA), 2019. Google Scholar
  17. Oded Goldreich. A brief introduction to property testing. In Studies in Complexity and Cryptography. Miscellanea on the Interplay between Randomness and Computation, pages 465-469. Springer, 2011. Google Scholar
  18. Oded Goldreich, Shafi Goldwasser, and Dana Ron. Property testing and its connection to learning and approximation. Journal of the ACM (JACM), 45(4):653-750, 1998. Google Scholar
  19. Michael Kapralov and Rina Panigrahy. Spectral sparsification via random spanners. In Proceedings of the 3rd Innovations in Theoretical Computer Science Conference, pages 393-398, 2012. Google Scholar
  20. Tali Kaufman, Michael Krivelevich, and Dana Ron. Tight bounds for testing bipartiteness in general graphs. SIAM Journal on computing, 33(6):1441-1483, 2004. Google Scholar
  21. Christoph Lenzen and Reut Levi. A Centralized Local Algorithm for the Sparse Spanning Graph Problem. In Proc. 45th Int. Colloq. Automata Lang. Prog. (ICALP), pages 87:1-87:14, 2018. Google Scholar
  22. Reut Levi, Guy Moshkovitz, Dana Ron, Ronitt Rubinfeld, and Asaf Shapira. Constructing near spanning trees with few local inspections. Random Structures &Algorithms, 50(2):183-200, 2017. Google Scholar
  23. Reut Levi and Dana Ron. A quasi-polynomial time partition oracle for graphs with an excluded minor. ACM Transactions on Algorithms (TALG), 11(3):24, 2015. Google Scholar
  24. Reut Levi, Dana Ron, and Ronitt Rubinfeld. Local Algorithms for Sparse Spanning Graphs. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, APPROX/RANDOM, pages 826-842, 2014. Google Scholar
  25. Reut Levi, Dana Ron, and Ronitt Rubinfeld. A local algorithm for constructing spanners in minor-free graphs. arXiv preprint, 2016. URL: http://arxiv.org/abs/1604.07038.
  26. Reut Levi, Ronitt Rubinfeld, and Anak Yodpinyanee. Local Computation Algorithms for Graphs of Non-constant Degrees. Algorithmica, 77(4):971-994, 2017. Google Scholar
  27. Yishay Mansour, Boaz Patt-Shamir, and Shai Vardi. Constant-time local computation algorithms. In International Workshop on Approximation and Online Algorithms, pages 110-121, 2015. Google Scholar
  28. Yishay Mansour, Aviad Rubinstein, Shai Vardi, and Ning Xie. Converting online algorithms to local computation algorithms. In Automata, Languages, and Programming - 39th International Colloquium, ICALP 2012, Warwick, UK, July 9-13, 2012, Proceedings, Part I, pages 653-664. Springer, 2012. Google Scholar
  29. Yishay Mansour and Shai Vardi. A local computation approximation scheme to maximum matching. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, pages 260-273. Springer, 2013. Google Scholar
  30. David Peleg. Distributed Computing: A Locality-sensitive Approach. SIAM, 2000. Google Scholar
  31. David Peleg and Alejandro A Schäffer. Graph spanners. Journal of graph theory, 13(1):99-116, 1989. Google Scholar
  32. David Peleg and Jeffrey D Ullman. An optimal synchronizer for the hypercube. SIAM Journal on computing, 18(4):740-747, 1989. Google Scholar
  33. Seth Pettie. Distributed algorithms for ultrasparse spanners and linear size skeletons. Distributed Computing, 22(3):147-166, 2010. Google Scholar
  34. Omer Reingold and Shai Vardi. New techniques and tighter bounds for local computation algorithms. Journal of Computer and System Sciences, 82(7):1180-1200, 2016. Google Scholar
  35. Ronitt Rubinfeld, Gil Tamir, Shai Vardi, and Ning Xie. Fast Local Computation Algorithms. In Innovations in Computer Science - ICS 2010, pages 223-238, 2011. Google Scholar
  36. Jeanette P Schmidt, Alan Siegel, and Aravind Srinivasan. Chernoff-Hoeffding bounds for applications with limited independence. SIAM J. Discrete Math., 8(2):223-250, 1995. Google Scholar
  37. Daniel A Spielman and Shang-Hua Teng. Spectral sparsification of graphs. SIAM Journal on Computing, 40(4):981-1025, 2011. Google Scholar
  38. Salil P. Vadhan. Pseudorandomness. Foundations and Trends in Theoretical Computer Science, 7(1-3):1-336, 2012. Google Scholar
  39. Rephael Wenger. Extremal graphs with no C4’s, C6’s, or C10’s. Journal of Combinatorial Theory, Series B, 52(1):113-116, 1991. 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