Coresets meet EDCs: Algorithms for matching and vertex cover on massive graphs

Sepehr Assadi, Mohammad Hossein Bateni, Aaron Bernstein, Vahab Mirrokni, Cliff Stein

    Research output: Contribution to conferencePaperpeer-review

    Abstract

    There is a rapidly growing need for scalable algorithms that solve classical graph problems, such as maximum matching and minimum vertex cover, on massive graphs. 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-2approximation for matching in random arrival streams that uses subquadratic space, namely a (1.5 + ε)-approximation streaming algorithm that uses Oe(n1.5) space for constant ε > 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 + ε)-approximation algorithm with Oe(mn + n) memory per machine for constant ε > 0. By building on our unified approach, we further develop parallel algorithms in the MPC model that give a (1+)-approximation to matching and an O(1)approximation to vertex cover in only O(log log n) MPC rounds and O(n/polylog(n)) memory per machine. These results settle multiple open questions posed by Czumaj et al. [STOC 2018]. We obtain our results by a novel combination of two previously disjoint set of techniques, namely randomized composable coresets and edge degree constrained subgraphs (EDCS). We significantly extend the power of these techniques and prove several new structural results. For example, we show that an EDCS is a sparse certificate for large matchings and small vertex covers that is quite robust to sampling and composition.

    Original languageEnglish (US)
    Pages1616-1635
    Number of pages20
    DOIs
    StatePublished - 2019
    Event30th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2019 - San Diego, United States
    Duration: Jan 6 2019Jan 9 2019

    Conference

    Conference30th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2019
    Country/TerritoryUnited States
    CitySan Diego
    Period1/6/191/9/19

    ASJC Scopus subject areas

    • Software
    • General Mathematics

    Fingerprint

    Dive into the research topics of 'Coresets meet EDCs: Algorithms for matching and vertex cover on massive graphs'. Together they form a unique fingerprint.

    Cite this