@inproceedings{a23040eccd1c4217aec2835b9b631b8c,

title = "Distributed coloring of hypergraphs",

abstract = "For any integer $$r \ge 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 $$\textrm{poly}(\log \log n)$$ -round randomized Local algorithm that computes a $$O(\varDelta ^{1/(r-1)})$$ -coloring w.h.p. This is tight up to polynomial factors of the time complexity as $$\varOmega (\log _\varDelta \log n)$$ distributed rounds are necessary for even obtaining a $$\varDelta $$ -coloring, where $$\varDelta $$ is the maximum degree, and tight up to logarithmic factors of the number of colors, as $$\varTheta ((\varDelta /\log \varDelta )^{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.",

keywords = "Congested Clique, Distributed computing, Hypergraph coloring, LOCAL model",

author = "Duncan Adamson and Halld{\'o}rsson, {Magn{\'u}s M.} and Alexandre Nolin",

note = "This project was supported by Icelandic Research Fund grant no. 217965. ; 30th International Colloquium on Structural Information and Communication Complexity, SIROCCO 2023 ; Conference date: 06-06-2023 Through 09-06-2023",

year = "2023",

month = may,

day = "25",

doi = "10.1007/978-3-031-32733-9_5",

language = "English",

isbn = "9783031327322",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

publisher = "Springer Science and Business Media",

pages = "89--111",

editor = "Sergio Rajsbaum and Alkida Balliu and Dennis Olivetti and Daymude, {Joshua J.}",

booktitle = "Structural Information and Communication Complexity - 30th International Colloquium, SIROCCO 2023, Proceedings",

address = "United States",

}