Distributed Binary Labeling Problems in High-Degree Graphs
CoRR(2023)
摘要
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 $\delta$ have constraints on the number of
selected incident edges. They showed that the deterministic round complexity of
any such problem is $O_{d,\delta}(1)$, $\Theta_{d,\delta}(\log n)$, or
$\Theta_{d,\delta}(n)$, or the problem is unsolvable. However, their
classification only addresses complexity as a function of $n$; here
$O_{d,\delta}$ hides constants that may depend on parameters $d$ and $\delta$.
In this work we study the complexity of binary labeling problems as a
function of all three parameters: $n$, $d$, and $\delta$. 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 $\Theta_{d,\delta}(\log
n)$, then the complexity for each $d$ and $\delta$ is always either
$\Theta(\log_d n)$, $\Theta(\log_\delta n)$, or $\Theta(\log n)$.
To prove our upper bounds, we introduce a new, more aggressive version of the
rake-and-compress technique that benefits from high-degree nodes.
更多查看译文
AI 理解论文
溯源树
样例
生成溯源树,研究论文发展脉络
Chat Paper
正在生成论文摘要