# Item

ITEM ACTIONSEXPORT

Released

Paper

#### A Local Algorithm for the Sparse Spanning Graph Problem

##### External Resource

No external resources are shared

##### Fulltext (restricted access)

There are currently no full texts shared for your IP range.

##### Fulltext (public)

arXiv:1703.05418.pdf

(Preprint), 165KB

##### Supplementary Material (public)

There is no public supplementary material available

##### Citation

Lenzen, C., & Levi, R. (2017). A Local Algorithm for the Sparse Spanning Graph Problem. Retrieved from http://arxiv.org/abs/1703.05418.

Cite as: https://hdl.handle.net/11858/00-001M-0000-002D-8AB0-4

##### Abstract

Constructing a sparse \emph{spanning subgraph} is a fundamental primitive in
graph theory. In this paper, we study this problem in the Centralized Local
model, where the goal is to decide whether an edge is part of the spanning
subgraph by examining only a small part of the input; yet, answers must be
globally consistent and independent of prior queries.
Unfortunately, maximally sparse spanning subgraphs, i.e., spanning trees,
cannot be constructed efficiently in this model. Therefore, we settle for a
spanning subgraph containing at most $(1+\varepsilon)n$ edges (where $n$ is the
number of vertices and $\varepsilon$ is a given approximation/sparsity
parameter). We achieve query complexity of
$\tilde{O}(poly(\Delta/\varepsilon)n^{2/3})$,\footnote{$\tilde{O}$-notation
hides polylogarithmic factors in $n$.} where $\Delta$ is the maximum degree of
the input graph. Our algorithm is the first to do so on arbitrary graphs.
Moreover, we achieve the additional property that our algorithm outputs a
\emph{spanner,} i.e., distances are approximately preserved. With high
probability, for each deleted edge there is a path of
$O(poly(\Delta/\varepsilon)\log^2 n)$ hops in the output that connects its
endpoints.