CISPA
Browse

File(s) not publicly available

Distributed Maximal Matching and Maximal Independent Set on Hypergraphs

conference contribution
posted on 2023-11-29, 18:25 authored by Alkida Balliu, Sebastian BrandtSebastian Brandt, Fabian Kuhn, Dennis Olivetti
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", }

Usage metrics

    Categories

    No categories selected

    Exports

    RefWorks
    BibTeX
    Ref. manager
    Endnote
    DataCite
    NLM
    DC