Local computation algorithms for graphs of non-constant degrees

DOI10.1007/S00453-016-0126-YMaRDI QIDQ524360zbMATH OpenOpenAlexFDO

Authors Reut Levi, Ronitt Rubinfeld, Anak Yodpinyanee

Publication date 2 May 2017

Published in Algorithmica (Search for Journal in Brave)

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

zbMATH Keywords

randomized algorithmsmaximal independent setmaximum matchinglocal computation algorithms

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25) Randomized algorithms (68W20) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Abstract: In the model of emph{local computation algorithms} (LCAs), we aim to compute the queried part of the output by examining only a small (sublinear) portion of the input. Many recently developed LCAs on graph problems achieve time and space complexities with very low dependence on $n$, the number of vertices. Nonetheless, these complexities are generally at least exponential in $d$, the upper bound on the degree of the input graph. Instead, we consider the case where parameter $d$ can be moderately dependent on $n$, and aim for complexities with subexponential dependence on $d$, while maintaining polylogarithmic dependence on $n$. We present: a randomized LCA for computing maximal independent sets whose time and space complexities are quasi-polynomial in $d$ and polylogarithmic in $n$; for constant $epsilon>0$, a randomized LCA that provides a $(1-epsilon)$-approximation to maximum matching whose time and space complexities are polynomial in $d$ and polylogarithmic in $n$.

Recommendations

• Constant-time local computation algorithms
• Constant-Time Local Computation Algorithms
• On the probe complexity of local computation algorithms
• Converting online algorithms to local computation algorithms
• New techniques and tighter bounds for local computation algorithms

Cites work

• A Local Computation Approximation Scheme to Maximum Matching
• A Simple Parallel Algorithm for the Maximal Independent Set Problem
• A fast and simple randomized parallel algorithm for maximal matching
• A fast and simple randomized parallel algorithm for the maximal independent set problem
• A local clustering algorithm for massive graphs and its application to nearly linear time graph partitioning
• A near-optimal sublinear-time algorithm for approximating the minimum vertex cover size
• A parallel algorithmic version of the local lemma
• Algorithms – ESA 2005
• An $n^{5/2} $ Algorithm for Maximum Matchings in Bipartite Graphs
• An algorithmic approach to the Lovász local lemma. I
• Approximating the distance to properties in bounded-degree and general sparse graphs
• Approximating the minimum vertex cover in sublinear time and a connection to distributed algorithms
• Converting online algorithms to local computation algorithms
• Deterministic stateless centralized local algorithms for bounded degree graphs
• Distributed Computing: A Locality-Sensitive Approach
• Distributed algorithms for the Lovász local lemma and graph coloring
• Distributed approximate matching
• Flow-based algorithms for local graph clustering
• Improved constant-time approximation algorithms for maximum matchings and other optimization problems
• Limits of local algorithms over sparse random graphs
• Local monotonicity reconstruction
• Local reconstructors and tolerant testers for connectivity and diameter
• Locality in Distributed Graph Algorithms
• New techniques and tighter bounds for local computation algorithms
• Noise tolerance of expanders and sublinear expansion reconstruction
• Online geometric reconstruction
• Property-preserving data reconstruction
• Pseudorandom generators without the XOR lemma (extended abstract)
• Space-efficient local computation algorithms
• Testing and reconstruction of Lipschitz functions with applications to data privacy
• The locality of distributed symmetry breaking

Cited in

(19)

• On the probe complexity of local computation algorithms
• Local improving algorithms for large cuts in graphs with maximum degree three
• Converting online algorithms to local computation algorithms
• Space-efficient local computation algorithms
• Average Sensitivity of Graph Algorithms
• Distributed algorithms for the Lovász local lemma and graph coloring
• On the recognition of families of graphs with local computations
• New techniques and tighter bounds for local computation algorithms
• Best of two local models: centralized local and distributed local algorithms
• When Algorithms for Maximal Independent Set and Maximal Matching Run in Sublinear Time
• Sparsifying distributed algorithms with ramifications in massively parallel computation and centralized local computation
• Can we locally compute sparse connected subgraphs?
• Local algorithms for bounded degree sparsifiers in sparse graphs
• Constant-time local computation algorithms
• Sublinear time algorithms and complexity of approximate maximum matching
• Foundations of Software Science and Computation Structures
• Local computation algorithms for spanners
• Node and edge averaged complexities of local graph problems
• Localization of edges in graph models of two-level algorithms

This page was built for publication: Local computation algorithms for graphs of non-constant degrees

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