Symmetry Breaking in the Congest Model: Time- and Message-Efficient Algorithms for Ruling Sets

Shreyas Pai, Gopal Pandurangan, Sriram V. Pemmaraju +2

We study local symmetry breaking problems in the CONGEST model, focusing on ruling set problems, which generalize the fundamental Maximal Independent Set (MIS) problem. A $\beta$-rulin…