Coresets meet EDCS: algorithms for matching and vertex cover on massive graphs

DOI10.1137/1.9781611975482.98MaRDI QIDQ5236282zbMATH OpenOpenAlexFDO

Authors Sepehr Assadi, MohammadHossein Bateni, Aaron Bernstein, Vahab S. Mirrokni, Clifford Stein

Publication date 15 October 2019

Published in Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms (Search for Journal in Brave)

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

Mathematics Subject Classification ID

Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Graph theory (including graph drawing) in computer science (68R10) Approximation algorithms (68W25) Analysis of algorithms (68W40)

Abstract: As massive graphs become more prevalent, there is a rapidly growing need for scalable algorithms that solve classical graph problems, such as maximum matching and minimum vertex cover, on large datasets. For massive inputs, several different computational models have been introduced, including the streaming model, the distributed communication model, and the massively parallel computation (MPC) model that is a common abstraction of MapReduce-style computation. In each model, algorithms are analyzed in terms of resources such as space used or rounds of communication needed, in addition to the more traditional approximation ratio. In this paper, we give a single unified approach that yields better approximation algorithms for matching and vertex cover in all these models. The highlights include: * The first one pass, significantly-better-than-2-approximation for matching in random arrival streams that uses subquadratic space, namely a $(1.5+epsilon)$-approximation streaming algorithm that uses $O(n^{1.5})$ space for constant $epsilon>0$. * The first 2-round, better-than-2-approximation for matching in the MPC model that uses subquadratic space per machine, namely a $(1.5+epsilon)$-approximation algorithm with $O(sqrtmn+n)$ memory per machine for constant $epsilon>0$. By building on our unified approach, we further develop parallel algorithms in the MPC model that give a $(1+epsilon)$-approximation to matching and an $O(1)$-approximation to vertex cover in only $O(loglogn)$ MPC rounds and $O(n/polylog(n))$ memory per machine. These results settle multiple open questions posed in the recent paper of Czumaj~et.al. [STOC 2018].

Recommendations

• Improved massively parallel computation algorithms for MIS, matching, and vertex cover
• Approximation, Randomization and Combinatorial Optimization. Algorithms and Techniques
• Approximating matching size from random streams
• Kernelization via Sampling with Applications to Finding Matchings and Related Problems in Dynamic Graph Streams
• Round compression for parallel matching algorithms

Cited in

(30)

• Distributed algorithms for matching in hypergraphs
• Equivalence classes and conditional hardness in massively parallel computations
• Breaking the linear-memory barrier in \(\mathsf{MPC}\): fast \(\mathsf{MIS}\) on trees with strongly sublinear memory
• Massively parallel entity matching with linear classification in low dimensional space
• Streaming and massively parallel algorithms for edge coloring
• Log diameter rounds algorithms for 2-vertex and 2-edge connectivity
• Round compression for parallel matching algorithms
• Improved massively parallel computation algorithms for MIS, matching, and vertex cover
• Round compression for parallel matching algorithms
• Deterministic dynamic matching in worst-case update time
• scientific article; zbMATH DE number 7758318 (Why is no real title available?)
• Component stability in low-space massively parallel computation
• Maliciously secure massively parallel computation for all-but-one corruptions
• On regularity lemma and barriers in streaming and dynamic matching
• Stochastic minimum vertex cover in general graphs: a 3/2-approximation
• Sublinear algorithms for (1.5+)-approximate matching
• Sublinear time algorithms and complexity of approximate maximum matching
• Improved MPC algorithms for MIS, matching, and coloring on trees and beyond
• Distributed maximum matching verification in CONGEST
• Distributed-prover interactive proofs
• Towards a unified theory of sparsification for matching problems
• Improved bounds for matching in random-order streams
• Constructing large matchings via query access to a maximal matching oracle
• Improved bounds for matching in random-order streams
• Weighted matching in the random-order streaming and robust communication models
• Massively parallel algorithms for approximate shortest paths
• Streaming graph algorithms in the massively parallel computation model
• Exponentially faster massively parallel maximal matching
• Beating two-thirds for random-order streaming matching
• Sublinear space graph algorithms in the continual release model

This page was built for publication: Coresets meet EDCS: algorithms for matching and vertex cover on massive graphs

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