Distributed Maximal Matching and Maximal Independent Set on Hypergraphs

We investigate the distributed complexity of maximal matching and maximal independent set (MIS) in hypergraphs in the LOCAL model. A maximal matching of a hypergraph H=(VH,EH) is a maximal disjoint set Msubseteq EH of hyperedges and an MIS Ssubseteq VH is a maximal set of nodes such that no hyperedge is fully contained in S. Both problems can be solved by a simple sequential greedy algorithm, which can be implemented naively in O(Delta r + log^* n) rounds, where Delta is the maximum degree, r is the rank, and n is the number of nodes. We show that for maximal matching, this naive algorithm is optimal in the following sense. Any deterministic algorithm for solving the problem requires Omega(minDelta r, logDelta r n) rounds, and any randomized one requires Omega(minDelta r, logDelta r log n) rounds. Hence, for any algorithm with a complexity of the form O(f(Delta, r) + g(n)), we have f(Delta, r) ∈ Omega(Delta r) if g(n) is not too large, and in particular if g(n) = log^* n (which is the optimal asymptotic dependency on n due to Linial's lower bound [FOCS'87]). Our lower bound proof is based on the round elimination framework, and its structure is inspired by a new round elimination fixed point that we give for the Delta-vertex coloring problem in hypergraphs. For the MIS problem on hypergraphs, we show that for Deltall r, there are significant improvements over the naive O(Delta r + log^* n)-round algorithm. We give two deterministic algorithms for the problem. We show that a hypergraph MIS can be computed in O(Delta2·log r + Delta·log r· log^* r + log^* n) rounds. We further show that at the cost of a worse dependency on Delta, the dependency on r can be removed almost entirely, by giving an algorithm with complexity DeltaO(Delta)·log^* r + O(log^* n).