Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



TR15-019 | 3rd February 2015 13:39

Constructing Near Spanning Trees with Few Local Inspections


Authors: Reut Levi, Guy Moshkovitz, Dana Ron, Ronitt Rubinfeld, Asaf Shapira
Publication: 3rd February 2015 14:19
Downloads: 2108


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'$ 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'$. Can this task be performed by inspecting only a {\it constant} number of edges in $G$?

Our main results are:

(1) 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'$ of $G$ using few s inspections. To this end we analyze a ``local'' version of a famous minimum-weight spanning tree algorithm.

(2) 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)}$.

ISSN 1433-8092 | Imprint