Document Open Access Logo

Local Algorithms for Sparse Spanning Graphs

Authors Reut Levi, Dana Ron, Ronitt Rubinfeld

PDF
Thumbnail PDF

File

LIPIcs.APPROX-RANDOM.2014.826.pdf
  • Filesize: 0.49 MB
  • 17 pages

Document Identifiers

Author Details

Reut Levi
Dana Ron
Ronitt Rubinfeld

Cite As Get BibTex

Reut Levi, Dana Ron, and Ronitt Rubinfeld. Local Algorithms for Sparse Spanning Graphs. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2014). Leibniz International Proceedings in Informatics (LIPIcs), Volume 28, pp. 826-842, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2014) https://doi.org/10.4230/LIPIcs.APPROX-RANDOM.2014.826

Abstract

We initiate the study of the problem of designing sublinear-time (local) algorithms that, given an edge (u,v) in a connected graph G=(V,E), decide whether (u,v) belongs to a sparse spanning graph G' = (V,E') of G. Namely, G' should be connected and |E'| should be upper bounded by (1+epsilon)|V| for a given parameter epsilon > 0. To this end the algorithms may query the incidence relation  of the graph G, and we seek algorithms whose query complexity and running time (per given edge (u,v)) is as small as possible. Such an algorithm may be randomized but (for a fixed choice of its random coins) its decision on different edges in the graph should be consistent with the same spanning graph G' and independent of the order of queries.

We first show that for general (bounded-degree) graphs, the query complexity  of any such algorithm must be Omega(sqrt{|V|}). This lower bound holds  for graphs that have high expansion. We then turn to design and analyze algorithms  both for graphs with high expansion (obtaining a result that roughly  matches the lower bound) and for graphs that are (strongly) non-expanding (obtaining  results in which the complexity does not depend on |V|). The complexity of the problem for graphs that do not fall into these two categories is left as an open question.

Subject Classification

Keywords
  • local
  • spanning graph
  • sparse

Metrics

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

References

  1. N. Ailon, B. Chazelle, S. Comandur, and D. Liu. Property-preserving data reconstruction. Algorithmica, 51(2):160-182, 2008. Google Scholar
  2. 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'12), pages 1132-1139, 2012. Google Scholar
  3. R. Andersen, C. Borgs, J. Chayes, J. Hopcroft, V. Mirrokni, and S. Teng. Local computation of pagerank contributions. Internet Mathematics, 5(1-2):23-45, 2008. Google Scholar
  4. R. Andersen, F. Chung, and K. Lang. Local graph partitioning using pagerank vectors. In FOCS'06: Proceedings of the 47th Annual IEEE Symposium on Foundations of Computer Science, pages 475-486, 2006. Google Scholar
  5. R. Andersen and Y. Peres. Finding sparse cuts locally using evolving sets. In Proceedings of the Forty-First Annual ACM Symposium on the Theory of Computing, pages 235-244, 2009. Google Scholar
  6. D. A. Bader and G. Cong. A fast, parallel spanning tree algorithm for symmetric multiprocessors (smps). J. Parallel Distrib. Comput., 65(9):994-1006, 2005. Google Scholar
  7. P. Berkhin. Bookmark-coloring algorithm for personalized pagerank computing. Internet Mathematics, 3(1):41-62, 2006. Google Scholar
  8. B. Bollobás. Random Graphs. Cambridge University Press, 2001. Google Scholar
  9. Z. Brakerski. Local property restoring. Unpublished manuscript, 2008. Google Scholar
  10. A. Campagna, A. Guo, and R. Rubinfeld. Local reconstructors and tolerant testers for connectivity and diameter. In Proceedings of the Seventeenth International Workshop on Randomization and Computation (RANDOM), pages 411-424, 2013. Google Scholar
  11. B. Chazelle, R. Rubinfeld, and L. Trevisan. Approximating the minimum spanning tree weight in sublinear time. SIAM Journal on Computing, 34(6):1370-1379, 2005. Google Scholar
  12. B. Chazelle and C. Seshadhri. Online geometric reconstruction. In Proceedings of the Twenty-Second Annual ACM Symposium on Computation Geometry (SoCG), pages 386 - 394, 2006. Google Scholar
  13. A. Dutta, R. Levi, D. Ron, and R. Rubinfeld. A simple online competitive adaptation of lempel-ziv compression with efficient random access support. In Proceedings of the Data Compression Conference (DCC), pages 113-122, 2013. Google Scholar
  14. A. Edelman, A. Hassidim, H. N. Nguyen, and K. Onak. An efficient partitioning oracle for bounded-treewidth graphs. In Proceedings of the Fifteenth International Workshop on Randomization and Computation (RANDOM), pages 530-541, 2011. Google Scholar
  15. A. Hassidim, J. A. Kelner, H. N. Nguyen, and K. Onak. Local graph partitions for approximation and testing. In Proceedings of the Fiftieth Annual Symposium on Foundations of Computer Science, pages 22-31, 2009. Google Scholar
  16. G. Jeh and J. Widom. Scaling personalized web search. In Proceedings of the 12th International Conference on World Wide Web, pages 271-279, 2003. Google Scholar
  17. M. Jha and S. Raskhodnikova. Testing and reconstruction of Lipschitz functions with applications to data privacy. In 2011 IEEE 52nd Annual Symposium on Foundations of Computer Science (FOCS), 2011. Google Scholar
  18. S. Kale, Y. Peres, and C. Seshadhri. Noise tolerance of expanders and sublinear expander reconstruction. In Proceedings of the Forty-Ninth Annual Symposium on Foundations of Computer Science, pages 719-728, 2008. Google Scholar
  19. J. B. Kruskal. On the shortest spanning subtree of a graph and the traveling salesman problem. Proceedings of the AMS, 7(1):48-50, 1956. Google Scholar
  20. S. Kutten and D. Peleg. Fast distributed construction of small k-dominating sets and applications. Journal of Algorithms, 28(1):40-66, 1998. Google Scholar
  21. R. Levi and D. Ron. A quasi-polynomial time partition oracle for graphs with an excluded minor. In 40th International Colloquium on Automata, Languages, and Programming (ICALP'13), pages 709-720, 2013. Google Scholar
  22. R. Levi and D. Ron. A quasi-polynomial time partition oracle for graphs with an excluded minor. CoRR, abs/1302.3417, 2013. Google Scholar
  23. Reut Levi, Dana Ron, and Ronitt Rubinfeld. Local algorithms for sparse spanning graphs. CoRR, abs/1402.3609, 2014. Google Scholar
  24. N. Linial. Locality in distributed graph algorithms. SIAM Journal on Computing, 21(1):193-201, 1992. Google Scholar
  25. L. Trevisan M. Sudan and S. Vadhan. Pseudorandom generators without the XOR lemma. In Proceedings of the Thirty-First Annual ACM Symposium on the Theory of Computing, pages 537-546, 1999. Google Scholar
  26. 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. Google Scholar
  27. 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. Google Scholar
  28. S. Marko and D. Ron. Distance approximation in bounded-degree and general sparse graphs. ACM Transactions on Algorithms, 5(2), 2009. Article number 22. Google Scholar
  29. A. Mayer, S. Naor, and L. Stockmeyer. Local computations on static and dynamic graphs. In Proceedings of the 3rd Israel Symposium on Theory and Computing Systems (ISTCS), 1995. Google Scholar
  30. M. Naor and L. Stockmeyer. What can be computed locally? SIAM Journal on Computing, 24(6):1259-1277, 1995. Google Scholar
  31. H. N. Nguyen and K. Onak. Constant-time approximation algorithms via local improvements. In Proceedings of the Forty-Ninth Annual Symposium on Foundations of Computer Science, pages 327-336, 2008. Google Scholar
  32. L. Orecchia and Z. A. Zhu. Flow-based algorithms for local graph clustering. CoRR, abs/1307.2855, 2013. Google Scholar
  33. M. Parnas and D. Ron. Approximating the minimum vertex cover in sublinear time and a connection to distributed algorithms. Theoretical Computer Science, 381(1-3):183-196, 2007. Google Scholar
  34. D. Peleg and V. Rubinovich. A near-tight lower bound on the time complexity of distributed minimum-weight spanning tree construction. SIAM Journal on Computing, 30(5):1427-1442, 2000. Google Scholar
  35. S. Pettie. Distributed algorithms for ultrasparse spanners and linear size skeletons. Distributed Computing, 22(3):147-166, 2010. Google Scholar
  36. S. Pettie and V. Ramachandran. Randomized minimum spanning tree algorithms using exponentially fewer random bits. ACM Transactions on Algorithms, 4(1), 2008. Google Scholar
  37. 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
  38. M. E. Saks and C. Seshadhri. Local monotonicity reconstruction. SIAM Journal on Computing, 39(7):2897-2926, 2010. Google Scholar
  39. T. Sarlos, A. Benczur, K. Csalogany, D. Fogaras, and B. Racz. To randomize or not to randomize: Space optimal summaries for hyperlink analysis. In Proceedings of the 15th International Conference on WorldWide Web, pages 297-306, 2006. Google Scholar
  40. D. Spielman and S. Teng. Nearly-linear time algorithms for graph partitioning, graph sparsification, and solving linear systems. In Proceedings of the Thirty-Sixth Annual ACM Symposium on the Theory of Computing, pages 81-90, 2004. Google Scholar
  41. Y. Yoshida, M. Yamamoto, and H. Ito. An improved constant-time approximation algorithm for maximum matchings. In Proceedings of the Forty-First Annual ACM Symposium on the Theory of Computing, pages 225-234, 2009. Google Scholar
  42. Z. A. Zhu, S. Lattanzi, and V. Mirrokni. A local algorithm for finding well-connected clusters. In Proceedings of the Thirtieth International Conference on Machine Learning, 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 About DROPS Imprint Privacy Contact