Distributed approximation of maximum independent set and maximum matching

DOI10.1145/3087801.3087806MaRDI QIDQ5368958zbMATH OpenOpenAlexWikidataFDO

Authors Keren Censor-Hillel, Mohsen Ghaffari, Gregory Schwartzman, Reuven Bar-Yehuda

Publication date 11 October 2017

Published in Proceedings of the ACM Symposium on Principles of Distributed Computing (Search for Journal in Brave)

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

Mathematics Subject Classification ID

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) Graph algorithms (graph-theoretic aspects) (05C85) Distributed algorithms (68W15) Approximation algorithms (68W25) Analysis of algorithms (68W40)

Abstract: We present a simple distributed $Delta$-approximation algorithm for maximum weight independent set (MaxIS) in the $mathsfCONGEST$ model which completes in $O(extttMIS(G)cdotlogW)$ rounds, where $Delta$ is the maximum degree, $extttMIS(G)$ is the number of rounds needed to compute a maximal independent set (MIS) on $G$, and $W$ is the maximum weight of a node. %Whether our algorithm is randomized or deterministic depends on the exttt{MIS} algorithm used as a black-box. Plugging in the best known algorithm for MIS gives a randomized solution in $O(lognlogW)$ rounds, where $n$ is the number of nodes. We also present a deterministic $O(Delta+lo{g}^{\ast }n)$-round algorithm based on coloring. We then show how to use our MaxIS approximation algorithms to compute a $2$-approximation for maximum weight matching without incurring any additional round penalty in the $mathsfCONGEST$ model. We use a known reduction for simulating algorithms on the line graph while incurring congestion, but we show our algorithm is part of a broad family of emph{local aggregation algorithms} for which we describe a mechanism that allows the simulation to run in the $mathsfCONGEST$ model without an additional overhead. Next, we show that for maximum weight matching, relaxing the approximation factor to ($2+varepsilon$) allows us to devise a distributed algorithm requiring $O(fraclogDeltaloglogDelta)$ rounds for any constant $varepsilon>0$. For the unweighted case, we can even obtain a $(1+varepsilon)$-approximation in this number of rounds. These algorithms are the first to achieve the provably optimal round complexity with respect to dependency on $Delta$.

Recommendations

• Distributed approximate maximum matching in the CONGEST model
• Improved Distributed Approximate Matching
• Distributed local approximation algorithms for maximum matching in graphs and hypergraphs
• Distributed approximate matching
• Improved deterministic distributed matching via rounding

Cited in

(26)

• Best of two local models: centralized local and distributed local algorithms
• A new distributed approximation algorithm for the maximum weight independent set problem
• Optimal distributed covering algorithms
• A log-star distributed maximal independent set algorithm for growth-bounded graphs
• Distributed Algorithm for Better Approximation of the Maximum Matching
• scientific article; zbMATH DE number 1303560 (Why is no real title available?)
• An Improved Distributed Algorithm for Maximal Independent Set
• Distributed approximate maximum matching in the CONGEST model
• Distributed set cover approximation: primal-dual with optimal locality
• Adapting local sequential algorithms to the distributed setting
• Distributed local approximation algorithms for maximum matching in graphs and hypergraphs
• Distributed Maximal Independent Set using Small Messages
• Lower Bounds for Distributed Sketching of Maximal Matchings and Maximal Independent Sets
• Brief Announcement: Improved Distributed Approximations for Maximum-Weight Independent Set
• Simple and local independent set approximation
• Node and edge averaged complexities of local graph problems
• The Complexity of Distributed Approximation of Packing and Covering Integer Linear Programs
• (1- ϵ )-Approximate Maximum Weighted Matching in poly(1/ ϵ , log n ) Time in the Distributed and Parallel Settings
• Loosely-Stabilizing Maximal Independent Set Algorithms with Unreliable Communications
• Improved distributed approximations for maximum independent set
• Distributed maximum matching verification in CONGEST
• Approximating bipartite minimum vertex cover in the Congest model
• The message complexity of distributed graph optimization
• Distributed fractional local ratio and independent set approximation
• Narrowing the \textsf{LOCAL-CONGEST} gaps in sparse networks via expander decompositions
• On the distributed complexity of the semi-matching problem

This page was built for publication: Distributed approximation of maximum independent set and maximum matching

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