Distributed Binary Labeling Problems in High-Degree Graphs
No Thumbnail Available
Access rights
embargoedAccess
URL
Journal Title
Journal ISSN
Volume Title
A4 Artikkeli konferenssijulkaisussa
This publication is imported from Aalto University research portal.
View publication in the Research portal (opens in new window)
Other link related to publication (opens in new window)
View publication in the Research portal (opens in new window)
Other link related to publication (opens in new window)
Date
2024
Department
Major/Subject
Mcode
Degree programme
Language
en
Pages
18
Series
Structural Information and Communication Complexity - 31st International Colloquium, SIROCCO 2024, Proceedings, pp. 402-419, Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) ; Volume 14662 LNCS
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 δ have constraints on the number of selected incident edges. They showed that the deterministic round complexity of any such problem is Od,δ(1), Θd,δ(logn), or Θd,δ(n), or the problem is unsolvable. However, their classification only addresses complexity as a function of n; here Od,δ 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 Θ(logdn), Θ(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.Description
Publisher Copyright: © The Author(s), under exclusive license to Springer Nature Switzerland AG 2024.
Keywords
Other note
Citation
Lievonen, H, Picavet, T & Suomela, J 2024, Distributed Binary Labeling Problems in High-Degree Graphs . in Y Emek (ed.), Structural Information and Communication Complexity - 31st International Colloquium, SIROCCO 2024, Proceedings . Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 14662 LNCS, Springer, pp. 402-419, International Colloquium on Structural Information and Communication Complexity, Vietri sul Mare, Italy, 27/05/2024 . https://doi.org/10.1007/978-3-031-60603-8_22