Brief Announcement: A Centralized Local Algorithm for the Sparse Spanning Graph Problem

Authors Christoph Lenzen, Reut Levi



PDF
Thumbnail PDF

File

LIPIcs.DISC.2017.57.pdf
  • Filesize: 414 kB
  • 3 pages

Document Identifiers

Author Details

Christoph Lenzen
Reut Levi

Cite AsGet BibTex

Christoph Lenzen and Reut Levi. Brief Announcement: A Centralized Local Algorithm for the Sparse Spanning Graph Problem. In 31st International Symposium on Distributed Computing (DISC 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 91, pp. 57:1-57:3, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)
https://doi.org/10.4230/LIPIcs.DISC.2017.57

Abstract

Constructing a sparse spanning subgraph is a fundamental primitive in graph theory. In this paper, we study this problem in the Centralized Local model, where the goal is to decide whether an edge is part of the spanning subgraph by examining only a small part of the input; yet, answers must be globally consistent and independent of prior queries. Unfortunately, maximally sparse spanning subgraphs, i.e., spanning trees, cannot be constructed efficiently in this model. Therefore, we settle for a spanning subgraph containing at most (1+epsilon)n edges (where n is the number of vertices and epsilon is a given approximation/sparsity parameter). We achieve a query complexity of O(poly(Delta/epsilon)n^(2/3)) (up to polylogarithmic factors in n) where Delta is the maximum degree of the input graph. Our algorithm is the first to do so on arbitrary bounded degree graphs. Moreover, we achieve the additional property that our algorithm outputs a spanner, i.e., distances are approximately preserved. With high probability, for each deleted edge there is a path of O(log n (Delta+log n)/epsilon) hops in the output that connects its endpoints.
Keywords
  • local
  • spanning graph
  • sparse

Metrics

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

References

  1. Michael Elkin and Ofer Neiman. Efficient algorithms for constructing very sparse spanners and emulators. In Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2017, Barcelona, Spain, Hotel Porta Fira, January 16-19, pages 652-669, 2017. Google Scholar
  2. Christoph Lenzen and Reut Levi. A local algorithm for the sparse spanning graph problem. CoRR, abs/1703.05418, 2017. URL: http://arxiv.org/abs/1703.05418.
  3. R. Levi, G. Moshkovitz, D. Ron, R. Rubinfeld, and A. Shapira. Constructing near spanning trees with few local inspections. Random Structures &Algorithms, pages n/a-n/a, 2016. URL: http://dx.doi.org/10.1002/rsa.20652.
  4. R. Levi and D. Ron. A quasi-polynomial time partition oracle for graphs with an excluded minor. ACM Trans. Algorithms, 11(3):24:1-24:13, 2015. Google Scholar
  5. R. Levi, D. Ron, and R. Rubinfeld. Local algorithms for sparse spanning graphs. In Proceedings of the Eighteenth International Workshop on Randomization and Computation (RANDOM), pages 826-842, 2014. Google Scholar
  6. Reut Levi and Moti Medina. A (centralized) local guide. Bulletin of EATCS, 2(122), 2017. Google Scholar
  7. D. Peleg and A. A. Schäffer. Graph spanners. Journal of Graph Theory, 13:99-116, 1989. Google Scholar
  8. D. Peleg and J. D. Ullman. An optimal synchronizer for the hypercube. SIAM Journal on Computing, 18:229-243, 1989. Google Scholar
  9. R. Rubinfeld, G. Tamir, S. Vardi, and N. Xie. Fast local computation algorithms. In Proceedings of The Second Symposium on Innovations in Computer Science (ICS), pages 223-238, 2011. 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