Distributed Symmetry Breaking on Power Graphs via Sparsification
Yannic Maus, Saku Peltonen, Jara Uitto · 2023
In this paper we present efficient distributed algorithms for classical symmetry breaking problems, maximal independent sets (MIS) and ruling sets, in power graphs. We work in the standard CONGEST model of distributed message passing, where the communication network is abstracted as a graph G. Typically, the problem instance in CONGEST is identical to the communication network G, that is, we perform the symmetry breaking in G. In this work, we consider a setting where the problem instance corresponds to a power graph Gk, where each node of the communication network G is connected to all of its k-hop neighbors.