Local algorithms for sparse spanning graphs

DOI10.4230/LIPICS.APPROX-RANDOM.2014.826zbMATH Open1360.05168arXiv1402.3609OpenAlexW2963161417MaRDI QIDQ2969665FDOQ2969665

Authors: Reut Levi, Dana Ron, Ronitt Rubinfeld 

Publication date: 22 March 2017

Abstract: Constructing a spanning tree of a graph is one of the most basic tasks in graph theory. We consider a relaxed version of this problem in the setting of local algorithms. The relaxation is that the constructed subgraph is a sparse spanning subgraph containing at most $(1+epsilon)n$ edges (where $n$ is the number of vertices and $epsilon$ is a given approximation/sparsity parameter). In the local setting, the goal is to quickly determine whether a given edge $e$ belongs to such a subgraph, without constructing the whole subgraph, but rather by inspecting (querying) the local neighborhood of $e$. The challenge is to maintain consistency. That is, to provide answers concerning different edges according to the same spanning subgraph. We first show that for general bounded-degree graphs, the query complexity of any such algorithm must be $Omega(sqrtn)$. This lower bound holds for constant-degree graphs that have high expansion. Next we design an algorithm for (bounded-degree) graphs with high expansion, obtaining a result that roughly matches the lower bound. We then turn to study graphs that exclude a fixed minor (and are hence non-expanding). We design an algorithm for such graphs, which may have an unbounded maximum degree. The query complexity of this algorithm is $poly(1/epsilon,h)$ (independent of $n$ and the maximum degree), where $h$ is the number of vertices in the excluded minor. Though our two algorithms are designed for very different types of graphs (and have very different complexities), on a high-level there are several similarities, and we highlight both the similarities and the differences.

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

Recommendations

• Local algorithms for sparse spanning graphs
• scientific article; zbMATH DE number 7376014
• Constructing near spanning trees with few local inspections
• A local algorithm for constructing spanners in minor-free graphs
• Local algorithms for graphs

zbMATH Keywords

local algorithmsparse spanning graph

Mathematics Subject Classification ID

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

Cited In (10)

• On the probe complexity of local computation algorithms
• Limits of local algorithms over sparse random graphs
• Title not available (Why is that?)
• Improved Local Computation Algorithm for Set Cover via Sparsification
• Local algorithms for bounded degree sparsifiers in sparse graphs
• Can we locally compute sparse connected subgraphs?
• A local algorithm for constructing spanners in minor-free graphs
• Local computation algorithms for spanners
• Local algorithms for sparse spanning graphs
• Constructing near spanning trees with few local inspections

This page was built for publication: Local algorithms for sparse spanning graphs

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