Local algorithms for bounded degree sparsifiers in sparse graphs

DOI10.4230/LIPICS.ITCS.2018.52MaRDI QIDQ4993322zbMATH OpenOpenAlexFDO

Authors Shay Solomon

Publication date 15 June 2021

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

zbMATH Keywords

arboricitybounded degreelocal algorithmsparsifier

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Graph theory (including graph drawing) in computer science (68R10) Approximation algorithms (68W25) Distributed algorithms (68W15)

Abstract: In graph sparsification, the goal has almost always been of {global} nature: compress a graph into a smaller subgraph ({sparsifier}) that maintains certain features of the original graph. Algorithms can then run on the sparsifier, which in many cases leads to improvements in the overall runtime and memory. This paper studies sparsifiers that have bounded (maximum) degree, and are thus {locally} sparse, aiming to improve local measures of runtime and memory. To improve those local measures, it is important to be able to compute such sparsifiers {locally}. We initiate the study of local algorithms for bounded degree sparsifiers in unweighted sparse graphs, focusing on the problems of vertex cover, matching, and independent set. Let $epsilon>0$ be a slack parameter and $alphage1$ be a density parameter. We devise local algorithms for computing: (1) A $(1+epsilon)$-vertex cover sparsifier of degree $O(alpha/epsilon)$, for any graph of {arboricity} $alpha$. (2) A $(1+epsilon)$-maximum matching sparsifier and also a $(1+epsilon)$-maximal matching sparsifier of degree $O(alpha/epsilon)$, for any graph of arboricity $alpha$. (3) A $(1+epsilon)$-independent set sparsifier of degree $O(alph{a}^2/epsilon)$, for any graph of average degree $alpha$. Our algorithms require only a single communication round in the standard message passing models of distributed computing, and moreover, they can be simulated locally in a trivial way. As an immediate application we can extend results from distributed computing and local computation algorithms that apply to graphs of degree bounded by $d$ to graphs of arboricity $O(d/epsilon)$ or average degree $O(d^2/epsilon)$, at the expense of increasing the approximation guarantee by a factor of $(1+epsilon)$. In particular, we can extend the plethora of recent local computation algorithms [...]

Recommendations

• Local algorithms for sparse spanning graphs
• Local algorithms for sparse spanning graphs
• A simple local 3-approximation algorithm for vertex cover
• scientific article; zbMATH DE number 7376014
• Sparsification—a technique for speeding up dynamic graph algorithms

Cites work

• scientific article; zbMATH DE number 6696497 (Why is no real title available?)
• scientific article; zbMATH DE number 1256718 (Why is no real title available?)
• scientific article; zbMATH DE number 1263225 (Why is no real title available?)
• A Distributed (2+ε)-Approximation for Vertex Cover in O(logδ/ε log log δ) Rounds
• A Fast Algorithm for Constructing Sparse Euclidean Spanners
• A Local Computation Approximation Scheme to Maximum Matching
• An $n^{5/2} $ Algorithm for Maximum Matchings in Bipartite Graphs
• An Optimal Synchronizer for the Hypercube
• Approximation Algorithms for Multicommodity-Type Problems with Guarantees Independent of the Graph Size
• Approximation algorithms for NP-complete problems on planar graphs
• Characterizing multiterminal flow networks and computing flows in networks of small treewidth
• Compact routing schemes with improved stretch
• Deterministic fully dynamic data structures for vertex cover and matching
• Deterministic stateless centralized local algorithms for bounded degree graphs
• Distributed Computing: A Locality-Sensitive Approach
• Dynamic \((1 + \epsilon)\)-approximate matchings: a density-sensitive approach
• Efficient bounds for the stable set, vertex cover and set packing problems
• Extensions and limits to vertex sparsification
• Fast Greedy Algorithms for Constructing Sparse Geometric Spanners
• Fast distributed approximation algorithm for the maximum matching problem in bounded arboricity graphs
• Faster fully dynamic matchings with small approximation ratios
• Fully Dynamic Maximal Matching in O (log n) Update Time
• Fully dynamic matching in bipartite graphs
• Local computation algorithms for graphs of non-constant degrees
• Local-on-average distributed tasks
• Maintaining a large matching and a small vertex cover
• Nearly-linear time algorithms for graph partitioning, graph sparsification, and solving linear systems
• New deterministic approximation algorithms for fully dynamic matching
• Optimal Euclidean spanners, really short, thin and lanky
• Optimal dynamic distributed MIS
• Orienting dynamic graphs, with applications to maximal matchings and adjacency queries
• Orienting fully dynamic graphs with worst-case time bounds
• Shortest augmenting paths for online matchings on trees
• Space-efficient local computation algorithms
• The locality of distributed symmetry breaking
• Vertex cover might be hard to approximate to within \(2 - \varepsilon \)

Cited in

(7)

• Limits of local algorithms over sparse random graphs
• scientific article; zbMATH DE number 7376014 (Why is no real title available?)
• Improved Local Computation Algorithm for Set Cover via Sparsification
• Efficient Distributed Decomposition and Routing Algorithms in Minor-Free Networks and Their Applications
• Matchings in low-arboricity graphs in the dynamic graph stream model
• Improved dynamic graph coloring
• Local algorithms for sparse spanning graphs

This page was built for publication: Local algorithms for bounded degree sparsifiers in sparse graphs

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