Local computation algorithms for graphs of non-constant degrees

DOI10.1007/S00453-016-0126-YzbMATH Open1360.68513arXiv1502.04022OpenAlexW1618811119MaRDI QIDQ524360FDOQ524360

Authors: Reut Levi, Ronitt Rubinfeld, Anak Yodpinyanee 

Publication date: 2 May 2017

Published in: Algorithmica (Search for Journal in Brave)

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$.

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

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

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)

Cites Work

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

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
• When Algorithms for Maximal Independent Set and Maximal Matching Run in Sublinear Time
• Best of two local models: centralized local and distributed local algorithms
• Sparsifying distributed algorithms with ramifications in massively parallel computation and centralized local computation
• Local algorithms for bounded degree sparsifiers in sparse graphs
• Can we locally compute sparse connected subgraphs?
• 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)