A graph is weakly 2-colored if the nodes are labeled with colors black and white such that each black node is adjacent to at least one white node and vice versa. In this work we study the distributed computational complexity of weak 2-coloring in the standard LOCAL model of distributed computing, and how it is related to the distributed computational complexity of other graph problems. First, we show that weak 2-coloring is a minimal distributed symmetry-breaking problem for regular trees and regular high-girth graphs: if there is any non-trivial locally checkable labeling problem that is solvable in o(log * n) rounds with a distributed graph algorithm in the middle of a regular tree, then weak 2-coloring is also solvable in o(log * n) rounds there. Second, we prove a tight lower bound of Ω(log * n) for the distributed computational complexity of weak 2-coloring in regular trees; previously only a lower bound of Ω(log log * n) was known. By minimality, the same lower bound holds for any non-trivial locally checkable problem inside regular trees. Prior work on distributed computational complexity. Formally, the model of computing that we study here is known as the LOCAL model of distributed computing [17, 21] : the same graph plays the dual role of being both the unknown input graph and the structure of the computer network, the nodes correspond to computers, the edges correspond to communication links, the nodes
Very recently, Balliu et al. REF refined our knowledge in this regard by proving a tight lower bound of Ωplog˚nq for weak 2-coloring on regular trees.
Hardness of minimal symmetry breaking in distributed computing
ArXiv
ArXiv
Computer Science