Constructing near spanning trees with few local inspections
Reut Levi, Guy Moshkovitz, Dana Ron, Ronitt Rubinfeld, A. Shapira · Random Structures and Algorithms · 2016
Abstract 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. LetGbe a connected bounded‐degree graph. Given an edgeeinGwe would like to decide whetherebelongs to a connected subgraph consisting of edges (for a prespecified constant ), where the decision for different edges should be consistent with the same subgraph . Can this task be performed by inspecting only aconstantnumber of edges inG? Our main results are: We show that if everyt‐vertex subgraph ofGhas expansion then one can (deterministically) construct a sparse spanning subgraph ofGusing 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 everyt‐vertex subgraph has expansion . 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. © 2016 Wiley Periodicals, Inc. Random Struct. Alg., 50, 183–200, 2017