Abstract
We initiate the study of the problem of designing sublineartime (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 (boundeddegree) 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) nonexpanding (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.
BibTeX  Entry
@InProceedings{levi_et_al:LIPIcs:2014:4741,
author = {Reut Levi and Dana Ron and Ronitt Rubinfeld},
title = {{Local Algorithms for Sparse Spanning Graphs}},
booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2014)},
pages = {826842},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783939897743},
ISSN = {18688969},
year = {2014},
volume = {28},
editor = {Klaus Jansen and Jos{\'e} D. P. Rolim and Nikhil R. Devanur and Cristopher Moore},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2014/4741},
URN = {urn:nbn:de:0030drops47410},
doi = {10.4230/LIPIcs.APPROXRANDOM.2014.826},
annote = {Keywords: local, spanning graph, sparse}
}
Keywords: 

local, spanning graph, sparse 
Collection: 

Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2014) 
Issue Date: 

2014 
Date of publication: 

04.09.2014 