A local algorithm for constructing spanners in minor-free graphs

DOI10.4230/LIPICS.APPROX-RANDOM.2016.38MaRDI QIDQ4636471zbMATH OpenOpenAlexFDO

Authors Reut Levi, Dana Ron, Ronitt Rubinfeld

Publication date 19 April 2018

Full work available at URL https://arxiv.org/abs/1604.07038

zbMATH Keywords

excluded-minorlocal algorithmsspannerssparse subgraphs

Mathematics Subject Classification ID

Distance in graphs (05C12) Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25)

Abstract: Constructing a spanning tree of a graph is one of the most basic tasks in graph theory. We consider this problem in the setting of local algorithms: one wants to quickly determine whether a given edge $e$ is in a specific spanning tree, without computing the whole spanning tree, but rather by inspecting the local neighborhood of $e$. The challenge is to maintain consistency. That is, to answer queries about different edges according to the same spanning tree. Since it is known that this problem cannot be solved without essentially viewing all the graph, we consider the relaxed version of finding a spanning subgraph with $(1+epsilon)n$ edges (where $n$ is the number of vertices and $epsilon$ is a given sparsity parameter). It is known that this relaxed problem requires inspecting $Omega(sqrtn)$ edges in general graphs, which motivates the study of natural restricted families of graphs. One such family is the family of graphs with an excluded minor. For this family there is an algorithm that achieves constant success probability, and inspects $(d/epsilon{)}^{poly(h)log(1/epsilon)}$ edges (for each edge it is queried on), where $d$ is the maximum degree in the graph and $h$ is the size of the excluded minor. The distances between pairs of vertices in the spanning subgraph $G^{\prime }$ are at most a factor of $poly(d,1/epsilon,h)$ larger than in $G$. In this work, we show that for an input graph that is $H$-minor free for any $H$ of size $h$, this task can be performed by inspecting only $poly(d,1/epsilon,h)$ edges. The distances between pairs of vertices in the spanning subgraph $G^{\prime }$ are at most a factor of $ildeO(hlog(d)/epsilon)$ larger than in $G$. Furthermore, the error probability of the new algorithm is significantly improved to $Theta(1/n)$. This algorithm can also be easily adapted to yield an efficient algorithm for the distributed setting.

Recommendations

• Local algorithms for sparse spanning graphs
• Constructing near spanning trees with few local inspections
• Local algorithms for sparse spanning graphs
• scientific article; zbMATH DE number 7376014
• Local Computation of Nearly Additive Spanners

Cited in

(9)

• Sparse covers for planar graphs and graphs that exclude a fixed minor
• Local algorithms for sparse spanning graphs
• Can we locally compute sparse connected subgraphs?
• Local algorithms for sparse spanning graphs
• Constructing near spanning trees with few local inspections
• scientific article; zbMATH DE number 7376014 (Why is no real title available?)
• Local computation algorithms for spanners
• Spanning adjacency oracles in sublinear time
• Nearly optimal local algorithms for constructing sparse spanners of clusterable graphs

This page was built for publication: A local algorithm for constructing spanners in minor-free graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4636471)