PaperlayerView exact revision on arXiv

Source-linked AI summary

Coresets Meet EDCS: Algorithms for Matching and Vertex Cover on Massive Graphs

Sepehr Assadi, MohammadHossein Bateni, Aaron Bernstein, Vahab Mirrokni, Cliff Stein

arXiv:1711.03076v3cs.DScs.DC

TL;DR

Massive-graph matching and vertex cover require algorithms that account for storage and communication constraints across computational models. The paper develops a unified randomized-composable-coreset approach and reports improved approximation results, including better-than-2 matching guarantees in streaming and MPC settings.

  • Problem

    Massive-graph matching and vertex-cover algorithms must scale beyond one processor, while unified approaches have often yielded weaker results than model-tailored algorithms.

    Source: §1 · p. 3

  • Method

    The paper develops a unified randomized-composable-coreset algorithmic framework for matching and vertex cover across streaming, communication, and MPC models.

    Source: §1 · p. 3

  • Results

    Across models, the algorithms improve approximation results; in random-arrival streams, one pass gives (3/2+ε)-approximate matching using eO(n^1.5) space.

    Source: §1 · p. 3

  • Takeaways & Limitations

    The low-space MPC results settle multiple open questions posed by Czumaj et al. [29].

    Source: §1 · p. 3

    For streaming, the adversarial-order lower bound does not preclude these bounds at eO(n^1.5) space, and proof prospects are linked to understanding Ruzsa–Szemerédi graphs.

    Source: §1.2 · p. 5

Abstract

from arXiv · show

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(\sqrt{mn} + 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(\log\log{n})$ MPC rounds and $O(n/poly\log{(n)})$ memory per machine. These results settle multiple open questions posed in the recent paper of Czumaj~et.al. [STOC 2018].

1 Introduction

The paper seeks scalable algorithms for matching and vertex cover across massive-graph computation models, where communication rounds and per-machine storage matter. It uses a unified randomized-composable-coreset approach to improve approximation results across those models.

1.1 Randomized Composable Coresets

  • Randomized composable coresets combine local subgraphs from random edge partitions, and constant-factor coresets for matching or vertex cover require Ω(n) size.Source: §1.1 · p. 4

1.2 First Result: Improved Algorithms via a New Randomized Coreset

  • eO(n)-size randomized composable coresets give (3/2+ε)-approximate maximum matching and (2+ε)-approximate minimum vertex cover with high probability.Source: §1.2 · p. 4
  • In random-arrival streams, one pass uses eO(n^1.5) space for a (3/2+ε)-approximate maximum matching.Source: §1.2 · p. 5
  • With eO(√mn+n) memory per machine, two MPC rounds give (3/2+ε)-approximate matching and (2+ε)-approximate vertex cover.Source: §1.2 · p. 5
  • On randomly partitioned inputs, simultaneous communication protocols achieve (3/2+ε)-approximate matching and (2+ε)-approximate vertex cover with eO(n) communication per player.Source: §1.2 · p. 6

1.3 Second Result: MPC with Low Space Per Machine

  • O(log log n) MPC rounds and O(n/polylog(n)) memory per machine suffice for a (1+ε)-approximate maximum matching and O(1)-approximate minimum vertex cover.Source: §1.3 · p. 6

1.4 Our Techniques

  • EDCS provide sparse certificates for matchings and vertex covers that remain robust to sampling and composition; recursive MPC processing uses EDCS on vertex-partitioned subgraphs without requiring cross-machine state consistency.Source: §1.4 · p. 7

1.5 Related Work

  • A prior (3/2)-approximation communication protocol for adversarially partitioned two-party inputs uses techniques completely disjoint from this paper’s.Source: §1.5 · p. 7

2 Preliminaries

The preliminaries establish graph notation, sampling conventions, and the MPC model, then state basic matching and vertex-cover facts and properties of EDCS. These EDCS properties support approximate matching preservation and a vertex-cover construction for the original graph.

2 Preliminaries

  • The notation section defines graph degrees and matching and vertex-cover sizes, and introduces martingales as sequences whose conditional expectation at each step equals the preceding variable.A summary of concentration bounds is provided in Appendix B.1.Source: §2 · p. 8
  • The preliminaries distinguish independent edge sampling from vertex sampling, which forms an induced subgraph on the sampled vertices.They also introduce graph notation and martingales, and point to concentration bounds in the appendix.Source: §2 · p. 8

2.1 The Massively Parallel Computation (MPC) Model

  • MPC computation uses synchronous rounds, with each machine performing local computation and exchanging messages that fit within its local memory.The model typically requires the number of machines and per-machine memory to be polynomially smaller than the input size.Source: §2.1 · p. 8

2.2 Basic Graph Theory Facts

  • For any graph, MM(G) ≤ VC(G) ≤ 2 · MM(G); if a matching and vertex cover satisfy α · |M| ≥ |V′|, both are α-approximations.A further fact relates a maximum-degree threshold to a lower bound on matching size.Source: §2.2 · p. 8
  • For maximum degree Δ and γ ∈ (0, 1), the vertices of degree at least γ · Δ imply MM(G) ≥ γ · Δ.The proof invokes Vizing’s theorem to obtain a matching from an edge coloring.Source: §2.2 · pp. 8–9

2.3 Edge Degree Constrained Subgraph (EDCS)

  • An EDCS H obeys degree-sum bounds β on its edges and β− on edges outside H, and one exists whenever β > β−.The section also reviews prior results that appropriately parameterized EDCSs preserve maximum matching approximately.Source: §2.3 · p. 9
  • For appropriate parameters, prior work shows an EDCS contains an almost 3/2-approximate maximum matching of G.The section notes that subsequent EDCS properties proved in this paper are new.Source: §2.3 · p. 9
  • Vhigh, the vertices with degree at least β−/2 in H, together with a minimum vertex cover of H covers G and has size at most (2 + ε) · VC(H).This holds for β ≥ 4/ε and β− ≥ β · (1 − ε/4).Source: §2.3 · p. 9

3 Warmup: A 3-Approximation Coreset for Matching

The section analyzes a simple matching coreset, proves a 3 + o(1) approximation under a matching-size assumption, and shows its approximation can approach 2 on some graphs.

3 Warmup: A 3-Approximation Coreset for Matching

  • A maximum matching from each random partition part forms an O(n)-size (3 + o(1))-approximation coreset when MM(G) = ω(k log n).The assumption is used because when it fails, the passage states an exact, non-randomized coreset is available.Source: §3 · p. 10

3.1 Concentration of Maximum Matching Size under Edge Sampling

  • Maximum matching size in an edge-sampled subgraph concentrates around its expectation, providing a building block for the coreset proof.The proof uses vertex-exposure martingales; changing the exposed edges incident to one vertex changes the maximum matching by at most 1.Source: §3.1 · pp. 10–11, §3 · p. 10

3.2 Proof of Theorem 4

  • The proof compares each part's matching with a fixed maximum matching of G, yielding a union coreset matching of size at least μ/3 − o(μ).It splits into whether the sampled residual matching is above μ/3 or many edges of the fixed maximum matching remain free to appear in the parts.Source: §3.2 · pp. 11–12

3.3 Lower Bound on Approximation Ratio of MaxMatching

  • Some graphs make MaxMatching's approximation ratio arbitrarily close to 2, so this coreset analysis cannot establish a ratio below 2.The lower-bound construction has maximum matching size n, while the union of selected part matchings can capture only about half that size.Source: §3.3 · p. 13

4 New Properties of Edge Degree Constrained Subgraphs

The section establishes that EDCS degree profiles are nearly unique and remain similar across sampled subgraphs, supporting their use in composable coresets and parallel algorithms.

4.1 Degree Distribution Lemma

  • For two EDCSs of the same graph, every vertex's degrees differ by at most O(log n) · λ^1/2 · β.The proof repeatedly expands sets of vertices whose degree differences are large, while the difference decreases only slightly at each step.Source: §4.1 · pp. 14–15

4.2 EDCS in Sampled Subgraphs

  • For two edge-sampled subgraphs, arbitrary EDCS choices have nearly matching degree profiles for every vertex with high probability, even when the samples are dependent.The stated bound assumes β ≥ 750 · λ^-2 · ln(n).Source: §4.2 · p. 16

4.2.2 EDCS in Vertex Sampled Subgraphs: Proof of Lemma 4.5

  • For vertex-sampled subgraphs, the degree comparison applies to vertices shared by both samples; vertices present in only one may have a large degree gap.The proof again uses an intersected EDCS and the degree-distribution lemma to compare the arbitrary EDCS choices.Source: §4.2 · p. 16, §4.2.2 · p. 18

4.2.1 EDCS in Edge Sampled Subgraphs: Proof of Lemma 4.4

  • In the edge-sampling proof, intersecting a suitable EDCS of the original graph with a sampled subgraph gives an EDCS of that subgraph with high probability.The degree-distribution lemma then compares arbitrary EDCS choices with these intersections.Source: §4.2.1 · pp. 16–17, §4.2 · p. 16

5 Randomized Coresets for Matching and Vertex Cover

The section constructs randomized matching and vertex-cover coresets by computing EDCSs on random graph partitions. Their union preserves EDCS structure and yields approximation guarantees for both problems.

5.1 Computing an EDCS from Random k-Partitions

  • Combining arbitrary EDCSs computed on random partition parts produces an EDCS for the original graph with probability 1 − 4/n^7.The resulting EDCS parameters are λ_C = O(log n) · λ^1/2 and β_C = (1 + λ_C) · k · β.Source: §5.1 · p. 19

5.2 EDCS as a Coreset for Matching and Vertex Cover

  • The union of local EDCSs is a (3/2 + ε)-approximation matching coreset of size O(n · β), with β = Θ(ε^-6 · log^7 n).The proof uses the matching guarantee for EDCSs on the union.Source: §5.2 · p. 20
  • For minimum vertex cover, local EDCSs plus vertices above the stated degree threshold form a (2 + ε)-approximation coreset of size O(n · β).The selected vertices are included directly in the final vertex cover.Source: §5.2 · p. 20
  • A polynomial-time implementation that approximates the final cover on the union instead of computing it exactly yields an almost 4-approximation.The remark distinguishes this implementation from the coreset guarantee, which neglects the time needed to compute a vertex cover in the union.Source: §5.2 · p. 20

6 MPC Algorithms for Matching and Vertex Cover

The MPC algorithm combines vertex-sampled EDCS subgraphs with recursive sparsification to handle smaller per-machine memory. It pairs high-degree vertices added to the vertex cover with a large matching incident on them, yielding constant-factor approximations.

6 MPC Algorithms for Matching and Vertex Cover

  • O(1)-approximation algorithms for matching and vertex cover use O(log log n) MPC rounds and O(n/polylog(n)) memory per machine.This is the stated result for the smaller-memory setting.Source: §6 · p. 21
  • Recursion on EDCS subgraphs alone could compound matching’s 3/2 approximation factor or give an O(log log n) vertex-cover approximation.The section addresses this by using matching and vertex cover as witnesses to each other.Source: §6 · p. 21
  • At each recursion, high-degree vertices added to the cover are paired with a large matching incident on those vertices, computable in O(1) parallel rounds.Their sizes remain within a constant factor, supporting constant approximations for both problems.Source: §6 · p. 21

6.1 A Parallel Algorithm for EDCS

  • ParallelEDCS samples vertex-induced subgraphs using limited independence; each vertex appears in Θ(p·k) subgraphs with high probability, and every input edge is sampled at least once.Limited independence reduces the per-edge communication from the naive Θ(p·k) messages to O(log n).Source: §6.1 · p. 22
  • The sampled subgraphs’ EDCSes are combined into a multigraph C that satisfies both EDCS properties with adjusted parameters.The proof separately establishes Property (P1) and Property (P2) for C.Source: §6.1 · pp. 23–24

6.2 Random Match Algorithm

RandomMatch finds a matching incident on a specified set S by sampling vertices in S, selecting edges to the complement, and retaining edges with unique endpoints. When S contains high-degree vertices, the resulting matching has expected size Θ(|S|).

6.2 Random Match Algorithm

  • RandomMatch samples each vertex in S independently with probability 1/2, then each sampled vertex chooses one edge to G\S uniformly at random.The chosen edges form Esmpl.Source: §6.2 · p. 24
  • The algorithm returns edges in Esmpl whose endpoints are both unique within Esmpl.A vertex outside S′ has degree exactly one in Esmpl with expected count Θ(|S|), supporting the matching-size bound.Source: §6.2 · pp. 24–25
  • E|M| = Θ(|S|) when every vertex in S has degree at least Δ/3 and the graph’s maximum degree Δ is at least 100 log n.This is the expected-size guarantee for RandomMatch on high-degree vertices.Source: §6.2 · p. 24

6.3 A Parallel Algorithm for Matching and Vertex Cover

ParallelAlgorithm recursively computes EDCS subgraphs, matches high-degree vertices, and removes covered or matched vertices before recursing. It returns constant-factor approximations to both matching and vertex cover.

6.3 A Parallel Algorithm for Matching and Vertex Cover

  • At each step, high-degree vertices added to the cover are accompanied by a matching of expected size Ω(|Vhigh|).This matching is found using RandomMatch on the EDCS and its high-degree vertices.Source: §6.3 · p. 26
  • The recursion takes T = O(log log Δ) steps because each recursive call reduces the maximum-degree bound to below Δ^(2/3).The base case computes a maximal matching locally.Source: §6.3 · pp. 25–26
  • All T steps use valid ParallelEDCS outputs with probability at least 1 − 1/n^4.Each step is valid with probability at least 1 − 1/n^5, and T = O(log log n).Source: §6.3 · p. 26
  • With constant probability, ParallelAlgorithm(G, n) outputs an O(1)-approximation to both maximum matching and minimum vertex cover.The matching and cover are feasible, and their sizes are within a constant factor with constant probability.Source: §6.3 · pp. 26–27

6.4 MPC Implementation of the Parallel Algorithm

The algorithm implements its EDCS and matching subroutines in constant MPC rounds per step, so the recursive algorithm runs in O(log log n) rounds. The section also describes how to reduce total system memory and extend the result to smaller per-machine memory.

6.4 MPC Implementation of the Parallel Algorithm

  • ParallelAlgorithm is implemented in O(log log n) MPC rounds using at most O(n) machines with eO(n) memory each.Its ParallelEDCS and RandomMatch calls each take O(1) MPC rounds.Source: §6.4 · p. 27

6.4.1 Optimizing the Number of Machines

  • Using the average degree instead of maximum degree reduces the machine count to eO(m/n) and total memory to eO(m).This modification is described as adhering to the strictest MPC total-memory restrictions.Source: §6.4.1 · p. 28

6.5 Extension to Smaller Memory Requirement and Proof of Theorem 7

  • The eO(n)-memory implementation yields O(1)-approximation algorithms for matching and vertex cover in O(log log n) rounds.The algorithm is extended to the full range of per-machine memory parameters s = n^Ω(1).Source: §6.5 · pp. 28–29

6.6 Further Improvements

The section extends the MPC matching algorithm to improve approximation guarantees, including a (1 + ε)-approximation through an adaptation of a streaming augmentation method. The adaptations use repeated matching calls and retain O(n/polylog(n)) memory per machine.

6.6.1 Proof of Corollary 8

  • An MPC algorithm computes a (2 + ε)-approximation to maximum matching of G with high probability in O(log (1/ε) · log log n) rounds, using O(n/polylog(n)) memory per machine.Source: §6.6 · p. 29

6.6 Further Improvements

  • (1 + ε)-approximate maximum matching takes (1/ε)O(1/ε) · (log log n) MPC rounds with O(n/polylog(n)) memory per machine.This is Corollary 9’s guarantee.Source: §6.6 · p. 29

6.6.2 Proof of Corollary 9

  • For Corollary 9, the algorithm adapts McGregor’s layered-graph approach by finding vertex-disjoint augmenting paths of length O(1/ε).When the matching is smaller than (1 − ε) · MM(G), some k = O(1/ε) yields many vertex-disjoint paths between the first and last layers with high probability.Source: §6.6.2 · p. 31
  • The layered-graph procedure grows disjoint paths through consecutive layers, backtracks from low-matching branches, and recurses after removing completed paths.The threshold balances limiting backtracks against avoiding incorrectly marking actual paths as dead ends.Source: §6.6.2 · p. 31
  • Replacing maximal matchings with O(1)-approximate matchings preserves the reduction with only a constant-factor increase in matching-subroutine calls between layers.The reduction analysis relies on the approximation ratio rather than maximality; implementing it in MPC gives the stated Corollary 9 round and memory bounds.Source: §6.6.2 · p. 32

A Some Applications of Randomized Composable Coresets

This section derives streaming, MPC, and simultaneous-communication algorithms from randomized composable coresets. The algorithms partition the input, compute and combine coresets, then solve the problem on the combined summary.

MPC Algorithms

  • In MPC, a randomized coreset algorithm yields a two-round algorithm whose output is an α-approximation with high probability.Machines build coresets for randomly partitioned graphs, then one machine collects their union and solves the problem on it.Source: A Some Applications of Randomized… · p. 38

Streaming Algorithms

  • In random-arrival streams, consecutive pieces form a random partition; the algorithm stores each piece temporarily, adds its coreset to H, and solves the problem on H at stream end.The piece size is chosen so that the resulting graphs have the distribution of a random partition.Source: A Some Applications of Randomized… · p. 38

Simultaneous Communication Model

  • In simultaneous communication, each party sends its coreset to a coordinator, which recovers an α-approximation with high probability.Each party’s communication is O(s) for a coreset of size s.Source: A Some Applications of Randomized… · pp. 38–39

Remark A.1

  • If efficient-time algorithms are required, solving the problem offline on the combined coresets gives approximation ratio ρ · α, where ρ is the offline algorithm’s guarantee.The remark notes that this blow-up can sometimes be avoided with additional care, but not in a black-box way.Source: A Some Applications of Randomized… · p. 39

B.1 Useful Concentration of Measure Inequalities

This appendix lists concentration inequalities used in the paper, including Azuma’s inequality for martingales and Chernoff bounds.

B.1 Useful Concentration of Measure Inequalities

  • Azuma’s inequality provides a concentration bound for martingales.Source: §B.1 · p. 39
  • The appendix states a Chernoff bound for independent random variables taking values in [0, 1].Source: §B.1 · p. 39
  • It also states a Chernoff-bound variant for κ-wise independent variables taking values in [0, 1].The supplied statement includes a condition relating κ, δ, and E[X].Source: §B.1 · p. 39

B.2 Proof of Lemma 2.4

The proof establishes that an EDCS exists by repeatedly fixing edges that violate its properties. A potential function increases at every step and is bounded, so the procedure terminates.

B.2 Proof of Lemma 2.4

  • Any graph G contains an EDCS(G, β, β−) for parameters β > β−.Source: §B.2 · p. 39
  • The procedure fixes a violating edge by removing it for a violation of Property (P1) or adding it for a violation of Property (P2).Source: §B.2 · p. 39
  • The potential increases by at least 1 per step and is at most O(n · β2), so the procedure terminates in O(n · β2) steps.The proof considers violations of each EDCS property and shows that fixing either increases the potential.Source: §B.2 · p. 40
Loading 1711.03076v3…