ausblenden:
Schlagwörter:
Computer Science, Data Structures and Algorithms, cs.DS
Zusammenfassung:
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(\sqrt{n})$ 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'$ 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'$ are at most a factor of $\tilde{O}(h\log(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.
