Distributed Binary Labeling Problems in High-Degree Graphs

Balliu et al. (DISC 2020) classified the hardness of solving binary labeling problems with distributed graph algorithms; in these problems the task is to select a subset of edges in a 2-colored tree in which white nodes of degree d and black nodes of degree δ have constraints on the number of selected incident edges. They showed that the deterministic round complexity of any such problem is O_d,δ(1), Θ_d,δ(logn), or Θ_d,δ(n), or the problem is unsolvable. However, their classification only addresses complexity as a function of n; here O_d,δ hides constants that may depend on parameters d and δ. In this work we study the complexity of binary labeling problems as a function of all three parameters: n, d, and δ. To this end, we introduce the family of structurally simple problems, which includes, among others, all binary labeling problems in which cardinality constraints can be represented with a context-free grammar. We classify possible complexities of structurally simple problems. As our main result, we show that if the complexity of a problem falls in the broad class of Θ_d,δ(logn), then the complexity for each d and δ is always either Θ(log_dn), Θ(log_δn), or Θ(logn). To prove our upper bounds, we introduce a new, more aggressive version of the rake-and-compress technique that benefits from high-degree nodes.