Improved Distributed Lower Bounds for MIS and Bounded (Out-)Degree Dominating Sets in Trees
Alkida Balliu, Sebastian Brandt, Fabian Kühn, Dennis Olivetti · 2021
Recently, Balliu, Brandt, and Olivetti [FOCS '20] showed the first ω(log n) lower bound for the maximal independent set (MIS) problem in trees. In this work we prove lower bounds for a much more relaxed family of distributed symmetry breaking problems. As a by-product, we obtain improved lower bounds for the distributed MIS problem in trees.