(2023) Distributed Maximal Matching and Maximal Independent Set on Hypergraphs.
Abstract
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).
| Item Type: | Conference or Workshop Item (A Paper) (Paper) |
|---|---|
| Divisions: | Sebastian Brandt (SB) |
| Conference: | SODA ACM/SIAM Symposium on Discrete Algorithms |
| Depositing User: | Sebastian Brandt |
| Date Deposited: | 12 Oct 2022 19:05 |
| Last Modified: | 12 Oct 2022 19:05 |
| Primary Research Area: | NRA1: Trustworthy Information Processing |
| URI: | https://publications.cispa.saarland/id/eprint/3802 |
Actions
Actions (login required)
 |
View Item |