Henrik Lievonen · Timothé Picavet · Jukka Suomela

Distributed binary labeling problems in high-degree graphs

SIROCCO 2024 · 31st International Colloquium on Structural Information and Communication Complexity, Vietri sul Mare, Italy, May 2024 · doi:10.1007/978-3-031-60603-8_22

authors’ version publisher’s version arXiv.org

Abstract

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.

Publication

Yuval Emek (Ed.): Structural Information and Communication Complexity, 31st International Colloquium, SIROCCO 2024, Vietri sul Mare, Italy, May 27-29, 2024, Proceedings, volume 14662 of Lecture Notes in Computer Science, pages 402–419, Springer, Berlin, 2024

ISBN 978-3-031-60603-8

This material is presented to ensure timely dissemination of scholarly and technical work. Copyright and all rights therein are retained by authors or by other copyright holders. All persons copying this information are expected to adhere to the terms and constraints invoked by each author’s copyright. In most cases, these works may not be reposted without the explicit permission of the copyright holder.