×

Constructing near spanning trees with few local inspections. (English) Zbl 1359.05022

Summary: Constructing a spanning tree of a graph is one of the most basic tasks in graph theory. Motivated by several recent studies of local graph algorithms, we consider the following variant of this problem. Let \(G\) be a connected bounded-degree graph. Given an edge \(e\) in \(G\) we would like to decide whether \(e\) belongs to a connected subgraph \(G^\prime\) consisting of \((1+\epsilon)n\) edges (for a prespecified constant \(\epsilon >0\)), where the decision for different edges should be consistent with the same subgraph \(G^\prime\). Can this task be performed by inspecting only a constant number of edges in \(G\)? Our main results are:
We show that if every \(t\)-vertex subgraph of \(G\) has expansion \(1/(\log t)^{1+o(1)}\) then one can (deterministically) construct a sparse spanning subgraph \(G^\prime\) of \(G\) using few inspections. To this end we analyze a “local” version of a famous minimum-weight spanning tree algorithm.
We show that the above expansion requirement is sharp even when allowing randomization. To this end we construct a family of 3-regular graphs of high girth, in which every \(t\)-vertex subgraph has expansion \(1/(\log t)^{1-o(1)}\). We prove that for this family of graphs, any local algorithm for the sparse spanning graph problem requires inspecting a number of edges which is proportional to the girth.

MSC:

05C05 Trees
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] Ailon, Property-preserving data reconstruction, Algorithmica 51 pp 160– (2008) · Zbl 1147.68017 · doi:10.1007/s00453-007-9075-9
[2] N. Alon R. Rubinfeld S. Vardi N. Xie Space-efficient local computation algorithms 2012 1132 1139
[3] N. Alon P. Seymour R. Thomas A separator theorem for graphs with an excluded minor and its applications 1990 293 299
[4] Andersen, Local computation of pagerank contributions, Internet Math 5 pp 23– (2008) · Zbl 1206.68346 · doi:10.1080/15427951.2008.10129302
[5] R. Andersen F. Chung K. Lang Local graph partitioning using pagerank vectors 2006 475 486
[6] R. Andersen Y. Peres Finding sparse cuts locally using evolving sets 2009 235 244 · Zbl 1304.05128
[7] Bader, A fast, parallel spanning tree algorithm for symmetric multiprocessors (smps), J Parallel Distrib Comput 65 pp 994– (2005) · Zbl 1101.68106 · doi:10.1016/j.jpdc.2005.03.011
[8] Berkhin, Bookmark-coloring algorithm for personalized pagerank computing, Internet Math 3 pp 41– (2006) · Zbl 1113.68375 · doi:10.1080/15427951.2006.10129116
[9] Z. Brakerski Local property restoring, Unpublished manuscript 2008 http://www.wisdom.weizmann.ac.il/ zvikab/localpapers/localrestore.pdf
[10] A. Campagna A. Guo R. Rubinfeld Local reconstructors and tolerant testers for connectivity and diameter 2013 411 424 · Zbl 1405.68239
[11] Chazelle, Approximating the minimum spanning tree weight in sublinear time, SIAM J Comput 34 pp 1370– (2005) · Zbl 1081.68120 · doi:10.1137/S0097539702403244
[12] B. Chazelle C. Seshadhri Online geometric reconstruction 2006 386 394 · Zbl 1153.68527
[13] Czumaj, Testing hereditary properties of nonexpanding bounded-degree graphs, SIAM J Comput 38 pp 2499– (2009) · Zbl 1191.68850 · doi:10.1137/070681831
[14] A. Dutta R. Levi D. Ron R. Rubinfeld A simple online competitive adaptation of lempel-ziv compression with efficient random access support 2013 113 122
[15] A. Hassidim J. A. Kelner H. N. Nguyen K. Onak Local graph partitions for approximation and testing 2009 22 31 · Zbl 1292.68126
[16] G. Jeh J. Widom Scaling personalized web search 2003 271 279
[17] M. Jha S. Raskhodnikova Testing and reconstruction of Lipschitz functions with applications to data privacy 2011 433 442
[18] S. Kale Y. Peres C. Seshadhri Noise tolerance of expanders and sublinear expander reconstruction 2008 719 728
[19] Kruskal, On the shortest spanning subtree of a graph and the traveling salesman problem, Proc AMS 7 pp 48– (1956) · Zbl 0070.18404 · doi:10.1090/S0002-9939-1956-0078686-7
[20] Kutten, Fast distributed construction of small k-dominating sets and applications, J Algorithms 28 pp 40– (1998) · Zbl 0919.68052 · doi:10.1006/jagm.1998.0929
[21] R. Levi D. Ron R. Rubinfeld Local algorithms for sparse spanning graphs 2014 826 842 · Zbl 1360.05168
[22] Linial, Locality in distributed graph algorithms, SIAM J Comput 21 pp 193– (1992) · Zbl 0787.05058 · doi:10.1137/0221015
[23] Lipton, A separator theorem for planar graphs, SIAM J Comput 36 pp 177– (1979) · Zbl 0432.05022
[24] L. Trevisan M. Sudan S. Vadhan Pseudorandom generators without the XOR lemma 1999 537 546 · Zbl 1345.68138
[25] Y. Mansour A. Rubinstein S. Vardi N. Xie Converting online algorithms to local computation algorithms 2012 653 664 · Zbl 1272.68471
[26] Y. Mansour S. Vardi A local computation approximation scheme to maximum matching 2013 260 273
[27] Marko, Distance approximation in bounded-degree and general sparse graphs, ACM Trans Algorithms 5 pp 22:1– (2009) · Zbl 1446.68197 · doi:10.1145/1497290.1497298
[28] A. Mayer S. Naor L. Stockmeyer Local computations on static and dynamic graphs 1995 268 278
[29] G. Moshkovitz A. Shapira Decomposing a graph into expanding subgraphs 2015 1283 1295
[30] Naor, What can be computed locally?, SIAM J Comput 24 pp 1259– (1995) · Zbl 0845.68006 · doi:10.1137/S0097539793254571
[31] H. N. Nguyen K. Onak Constant-time approximation algorithms via local improvements 2008 327 336
[32] L. Orecchia Z. A. Zhu Flow-based algorithms for local graph clustering 2013
[33] Parnas, Approximating the minimum vertex cover in sublinear time and a connection to distributed algorithms, Theor Comput Sci 381 pp 183– (2007) · Zbl 1188.68358 · doi:10.1016/j.tcs.2007.04.040
[34] Peleg, A near-tight lower bound on the time complexity of distributed minimum-weight spanning tree construction, SIAM J Comput 30 pp 1427– (2000) · Zbl 0973.05074 · doi:10.1137/S0097539700369740
[35] Pettie, Distributed algorithms for ultrasparse spanners and linear size skeletons, Distributed Comput 22 pp 147– (2010) · Zbl 1267.68314 · doi:10.1007/s00446-009-0091-7
[36] R. Rubinfeld G. Tamir S. Vardi N. Xie Fast local computation algorithms 2011 223 238
[37] Saks, Local monotonicity reconstruction, SIAM J Comput 39 pp 2897– (2010) · Zbl 1213.68420 · doi:10.1137/080728561
[38] T. Sarlos A. Benczur K. Csalogany D. Fogaras B. Racz To randomize or not to randomize: Space optimal summaries for hyperlink analysis 2006 297 306
[39] D. Spielman S. Teng Nearly-linear time algorithms for graph partitioning, graph sparsification, and solving linear systems 2004 81 90 · Zbl 1192.65048
[40] Y. Yoshida M. Yamamoto H. Ito An improved constant-time approximation algorithm for maximum matchings 2009 225 234 · Zbl 1304.05112
[41] Z. A. Zhu S. Lattanzi V. Mirrokni A local algorithm for finding well-connected clusters 2013 396 404
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.