Distributed Local Approximation Algorithms for Maximum Matching in Graphs and Hypergraphs

DOI10.1137/19M1279241zbMATH Open1445.05098arXiv1807.07645MaRDI QIDQ5115699FDOQ5115699

David G. Harris

Publication date: 18 August 2020

Published in: SIAM Journal on Computing (Search for Journal in Brave)

Abstract: We describe approximation algorithms in Linial's classic LOCAL model of distributed computing to find maximum-weight matchings in a hypergraph of rank $r$. Our main result is a deterministic algorithm to generate a matching which is an $O(r)$-approximation to the maximum weight matching, running in $ildeO(rlogDelta+lo{g}^{2}Delta+lo{g}^{*}n)$ rounds. (Here, the $ildeO()$ notations hides $extpolyloglogDelta$ and $extpolylogr$ factors). This is based on a number of new derandomization techniques extending methods of Ghaffari, Harris & Kuhn (2017). As a main application, we obtain nearly-optimal algorithms for the long-studied problem of maximum-weight graph matching. Specifically, we get a $(1+epsilon)$ approximation algorithm using $ildeO(logDelta/epsilo{n}^3+extpolylog(1/epsilon,loglogn))$ randomized time and $ildeO(lo{g}^{2}Delta/epsilo{n}^4+lo{g}^{*}n/epsilon)$ deterministic time. The second application is a faster algorithm for hypergraph maximal matching, a versatile subroutine introduced in Ghaffari et al. (2017) for a variety of local graph algorithms. This gives an algorithm for $(2Delta-1)$-edge-list coloring in $ildeO(lo{g}^{2}Deltalogn)$ rounds deterministically or $ildeO((loglogn{)}^3)$ rounds randomly. Another consequence (with additional optimizations) is an algorithm which generates an edge-orientation with out-degree at most $lceil(1+epsilon)lambdaceil$ for a graph of arboricity $lambda$; for fixed $epsilon$ this runs in $ildeO(lo{g}^{6}n)$ rounds deterministically or $ildeO(lo{g}^{3}n)$ rounds randomly.

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

zbMATH Keywords

matchingderandomizationhypergraphedge coloringLOCALNash-Williams decomposition

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Extremal problems in graph theory (05C35) Small world graphs, complex networks (graph-theoretic aspects) (05C82) Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Approximation algorithms (68W25) Hypergraphs (05C65) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Cites Work

• Title not available (Why is that?)
• Distributed Computing: A Locality-Sensitive Approach
• A simpler linear time \( \frac{2}{3} - \varepsilon\) approximation for maximum weight matching
• A Simple Parallel Algorithm for the Maximal Independent Set Problem
• Locality in Distributed Graph Algorithms
• Chernoff–Hoeffding Bounds for Applications with Limited Independence
• Improved Distributed Approximate Matching
• Concentration and Moment Inequalities for Polynomials of Independent Random Variables
• The Locality of Distributed Symmetry Breaking
• The price of being near-sighted
• Some simple distributed algorithms for sparse networks
• Distributed Approximate Matching
• Approximating weighted matchings in parallel
• Distributed Algorithm for Better Approximation of the Maximum Matching
• Distributed Approximation of Maximum Independent Set and Maximum Matching
• An Improved Distributed Algorithm for Maximal Independent Set
• Decomposition of Graphs Into Closed and Endless Chains
• Deterministic distributed edge-coloring with fewer colors
• A deterministic distributed 2-approximation for weighted vertex cover in \(O(\log N\log\varDelta/\log^2\log\varDelta)\) rounds
• Distributed Degree Splitting, Edge Coloring, and Orientations
• Derandomized Concentration Bounds for Polynomials, and Hypergraph Maximal Independent Set
• Improved deterministic distributed matching via rounding
• Distributed Approximate Maximum Matching in the CONGEST Model.

Cited In (7)

• Title not available (Why is that?)
• Distributed maximum maintenance on hierarchically divided graphs
• On the distributed complexity of the semi-matching problem
• Distributed coloring of hypergraphs
• A Local Computation Approximation Scheme to Maximum Matching
• On the Locality of Nash-Williams Forest Decomposition and Star-Forest Decomposition
• Distributed Algorithm for Better Approximation of the Maximum Matching

This page was built for publication: Distributed Local Approximation Algorithms for Maximum Matching in Graphs and Hypergraphs

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