English
 
Help Privacy Policy Disclaimer
  Advanced SearchBrowse

Item

ITEM ACTIONSEXPORT

Released

Paper

Constructing Near Spanning Trees with Few Local Inspections

MPS-Authors
There are no MPG-Authors in the publication available
External Resource
No external resources are shared
Fulltext (restricted access)
There are currently no full texts shared for your IP range.
Fulltext (public)

arXiv:1502.00413.pdf
(Preprint), 243KB

Supplementary Material (public)
There is no public supplementary material available
Citation

Levi, R., Moshkovitz, G., Ron, D., Rubinfeld, R., & Shapira, A. (2015). Constructing Near Spanning Trees with Few Local Inspections. Retrieved from http://arxiv.org/abs/1502.00413.


Cite as: https://hdl.handle.net/11858/00-001M-0000-002C-600D-C
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 $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 {\em 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 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)}$.