CISPA
Browse
SIROCCO2023_hypergraph_author_proof.pdf (637.25 kB)

Distributed Coloring of Hypergraphs

Download (637.25 kB)
conference contribution
posted on 2024-03-26, 09:24 authored by Duncan Adamson, Magnús M Halldórsson, Alexandre Nolin

For any integer r≥2, a linear r-uniform hypergraph is a generalization of ordinary graphs, where edges contain r vertices and two edges intersect in at most one node. We consider the problem of coloring such hypergraphs in several constrained models of computing, i.e., computing a partition such that no edge is fully contained in the same class. In particular, we give a poly(log⁡ log⁡ n)-round randomized LOCAL algorithm that computes a {\displaystyle {\mathcal O(Δ1/(r−1))-coloring w.h.p. This is tight up to polynomial factors of the time complexity as Ω(logΔ⁡log n) distributed rounds are necessary for even obtaining a Δ-coloring, where Δ is the maximum degree, and tight up to logarithmic factors of the number of colors, as Θ((Δ/log⁡Δ)1/(r−1)) colors are necessary for existence. We also give simple algorithms that run in O(1)-rounds of the CONGESTED CLIQUE model and in a single-pass of the semi-streaming model. 

History

Primary Research Area

  • Algorithmic Foundations and Cryptography

Name of Conference

Structural Information and Communication Complexity (SIROCCO)

Volume

13892

Page Range

89-111

Publisher

Springer Nature

Open Access Type

  • Not Open Access

BibTeX

@inproceedings{Adamson:Halldórsson:Nolin:2023, title = "Distributed Coloring of Hypergraphs", author = "Adamson, Duncan" AND "Halldórsson, Magnús M" AND "Nolin, Alexandre", year = 2023, month = 5, pages = "89--111", publisher = "Springer Nature", issn = "1611-3349", doi = "10.1007/978-3-031-32733-9_5" }