2020/09/21 by Hanguir, Oussama, Stein, Clifford
#Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences
paper · doi:10.48550/arxiv.2009.09605
We study the d-Uniform Hypergraph Matching (d-UHM) problem: given an n-vertex hypergraph G where every hyperedge is of size d, find a maximum cardinality set of disjoint hyperedges. For d≥3, the problem of finding the maximum matching is NP-complete, and was one of Karp's 21 NP-complete problems. In this paper we are interested in the problem of finding matchings in hypergraphs in the massively parallel computation (MPC) model that is a common abstraction of MapReduce-style computation. In this model, we present the first three parallel algorithms for d-Uniform Hypergraph Matching, and we analyse them in terms of resources such as memory usage, rounds of communication needed, and approximation ratio. The highlights include: \bullet A O(log n)-round d-approximation algorithm that uses O(nd) space per machine. \bullet A 3-round, O(d2)-approximation algorithm that uses O(√(nm)) space per machine. \bullet A 3-round algorithm that computes a subgraph containing a (d-1+(1)/(d))2-approximation, using O(√(nm)) space per machine for linear hypergraphs, and O(n√(nm)) in general.