LIPIcs.ICALP.2018.87.pdf
- Filesize: 481 kB
- 14 pages
Document
A Centralized Local Algorithm for the Sparse Spanning Graph Problem
Authors
Reut Levi 
-
Part of:
Volume:
45th International Colloquium on Automata, Languages, and Programming (ICALP 2018)
Series: Leibniz International Proceedings in Informatics (LIPIcs)
Conference: International Colloquium on Automata, Languages, and Programming (ICALP) - License:
Creative Commons Attribution 3.0 Unported license
- Publication Date: 2018-07-04
File
Document Identifiers
Author Details
Cite AsGet BibTex
Christoph Lenzen and Reut Levi. A Centralized Local Algorithm for the Sparse Spanning Graph Problem. In 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 107, pp. 87:1-87:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
https://doi.org/10.4230/LIPIcs.ICALP.2018.87
https://doi.org/10.4230/LIPIcs.ICALP.2018.87
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}), 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 spanning subgraph of bounded stretch 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.
Subject Classification
ACM Subject Classification
- Theory of computation → Sparsification and spanners
Keywords
- local
- spanning graph
- sparse
Metrics
- Access Statistics
-
Total Accesses (updated on a weekly basis)
0PDF Downloads
References
-
N. Alon, R. Rubinfeld, S. Vardi, and N. Xie. Space-efficient local computation algorithms. In Proceedings of the Twenty-Third Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 1132-1139, 2012.
-
Artur Czumaj, Oded Goldreich, Dana Ron, C. Seshadhri, Asaf Shapira, and Christian Sohler. Finding cycles and trees in sublinear time. Random Structures and Algorithms, 45(2):139-184, 2014.
-
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.
- G. Even, M. Medina, and D. Ron. Deterministic stateless centralized local algorithms for bounded degree graphs. In Algorithms - ESA 2014 - 22th Annual European Symposium, Wroclaw, Poland, September 8-10, 2014. Proceedings, pages 394-405, 2014. URL: http://dx.doi.org/10.1007/978-3-662-44777-2_33.
-
U. Feige, Y Mansour, and R. E. Schapire. Learning and inference in the presence of corrupted inputs. In Proceedings of The 28th Conference on Learning Theory, COLT 2015, Paris, France, July 3-6, 2015, pages 637-657, 2015.
-
Hendrik Fichtenberger, Reut Levi, Yadu Vasudev, and Maximilian Wötzel. On testing minor-freeness in bounded degree graphs with one-sided error. Unpublished manuscript, 2017.
- R. Levi, G. Moshkovitz, D. Ron, R. Rubinfeld, and A. Shapira. Constructing near spanning trees with few local inspections. Random Structures &Algorithms, 50:n/a-n/a, 2016. URL: http://dx.doi.org/10.1002/rsa.20652.
-
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.
-
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.
- R. Levi, D. Ron, and R. Rubinfeld. Local algorithms for sparse spanning graphs. CoRR, abs/1402.3609, 2014. URL: http://arxiv.org/abs/1402.3609.
-
R. Levi, R. Rubinfeld, and A. Yodpinyanee. Local computation algorithms for graphs of non-constant degrees. Algorithmica, pages 1-24, 2016.
-
Y. Mansour, A. Rubinstein, S. Vardi, and N. Xie. Converting online algorithms to local computation algorithms. In Automata, Languages and Programming: Thirty-Ninth International Colloquium (ICALP), pages 653-664, 2012.
-
Y. Mansour and S. Vardi. A local computation approximation scheme to maximum matching. In Proceedings of the Sixteenth International Workshop on Approximation Algorithms for Combinatorial Optimization Problems (APPROX), pages 260-273, 2013.
-
D. Peleg and A. A. Schäffer. Graph spanners. Journal of Graph Theory, 13:99-116, 1989.
-
D. Peleg and J. D. Ullman. An optimal synchronizer for the hypercube. SIAM Journal on Computing, 18:229-243, 1989.
-
L. S. Ram and E. Vicari. Distributed small connected spanning subgraph: Breaking the diameter bound. Technical report, ETH Zürich, 2011.
-
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.
- Ronitt Rubinfeld. Can we locally compute sparse connected subgraphs? In Computer Science - Theory and Applications - 12th International Computer Science Symposium in Russia, CSR 2017, Kazan, Russia, June 8-12, 2017, Proceedings, pages 38-47, 2017. URL: http://dx.doi.org/10.1007/978-3-319-58747-9_6.