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=(V_H,E_H) is a maximal disjoint set M ⊆ E_H of hyperedges and an MIS S ⊆ V_H 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(∆r + log* n) rounds, where ∆ is the maximum degree, r is the rank, and n is the number of nodes of the hypergraph.
We show that for maximal matching, this naive algorithm is optimal in the following sense. Any deterministic algorithm for solving the problem requires Ω(min{∆r, log_{∆r} n}) rounds, and any randomized one requires Ω(min{∆r, log_{∆r} log n}) rounds. Hence, for any algorithm with a complexity of the form O(f(∆,r) + g(n)), we have f(∆,r) ∈ Ω(∆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 ∆-vertex coloring problem in hypergraphs, where nodes need to be colored such that there are no monochromatic hyperedges.
For the MIS problem on hypergraphs, we show that for ∆ ≪ r, there are significant improvements over the naive O(∆r + log* n)-round algorithm. We give two deterministic algorithms for the problem. We show that a hypergraph MIS can be computed in O(∆^2 · log r + ∆ · log r · log* r + log* n) rounds. We further show that at the cost of a much worse dependency on ∆, the dependency on r can be removed almost entirely, by giving an algorithm with round complexity ∆^{O(∆)} · log* r + O(log* n).
History
Preferred Citation
Alkida Balliu, Sebastian Brandt, Fabian Kuhn and Dennis Olivetti. Distributed Maximal Matching and Maximal Independent Set on Hypergraphs. In: ACM-SIAM Symposium on Discrete Algorithms (SODA). 2023.
Primary Research Area
Algorithmic Foundations and Cryptography
Name of Conference
ACM-SIAM Symposium on Discrete Algorithms (SODA)
Legacy Posted Date
2022-10-12
Open Access Type
Gold
BibTeX
@inproceedings{cispa_all_3802,
title = "Distributed Maximal Matching and Maximal Independent Set on Hypergraphs",
author = "Balliu, Alkida and Brandt, Sebastian and Kuhn, Fabian and Olivetti, Dennis",
booktitle="{ACM-SIAM Symposium on Discrete Algorithms (SODA)}",
year="2023",
}