Constructing near spanning trees with few local inspections |
| |
| Authors: | Reut Levi Guy Moshkovitz Dana Ron Ronitt Rubinfeld Asaf Shapira |
| |
| Institution: | 1. MPI for Informatics, Saarbrücken, Germany;2. School of Mathematics, Tel Aviv University, Tel Aviv, Israel;3. School of Electrical Engineering, Tel Aviv University, Tel Aviv, Israel;4. CSAIL, MIT, Cambridge, Massachusetts |
| |
| 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. 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  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 a constant number of edges in G ? Our main results are: - We show that if every t‐vertex subgraph of G has expansion
 then one can (deterministically) construct a sparse spanning subgraph  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
 . 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 |
| |
| Keywords: | graph expansion local algorithms sparse spanning graph |
|
|
