2021/02/19 by Yi‐Jun Chang, Chang, Yi-Jun, Mohsen Ghaffari +1
Computer Science · #Complexity and Algorithms in Graphs #Cryptography and Data Security #Data Structures and Algorithms (cs.DS) #Distributed #FOS: Computer and information sciences #Parallel #Privacy-Preserving Technologies in Data #and Cluster Computing (cs.DC)
paper · pdf · doi:10.48550/arxiv.2102.09820
openalex publication_date 2021/02/19 · openalex created_date 2025/10/10 · openalex updated_date 2026/08/01
Network decomposition is a central concept in the study of distributed graph algorithms. We present the first polylogarithmic-round deterministic distributed algorithm with small messages that constructs a strong-diameter network decomposition with polylogarithmic parameters. Concretely, a (C, D) strong-diameter network decomposition is a partitioning of the nodes of the graph into disjoint clusters, colored with C colors, such that neighboring clusters have different colors and the subgraph induced by each cluster has a diameter at most D. In the weak-diameter variant, the requirement is relaxed by measuring the diameter of each cluster in the original graph, instead of the subgraph induced by the cluster. A recent breakthrough of Rozhoň and Ghaffari [STOC 2020] presented the first poly(log n)-round deterministic algorithm for constructing a weak-diameter network decomposition where C and D are both in poly(log n). Their algorithm uses small O(log n)-bit messages. One can transform their algorithm to a strong-diameter network decomposition algorithm with similar parameters. However, that comes at the expense of requiring unbounded messages. The key remaining qualitative question in the study of network decompositions was whether one can achieve a similar result for strong-diameter network decompositions using small messages. We resolve this question by presenting a novel technique that can transform any black-box weak-diameter network decomposition algorithm to a strong-diameter one, using small messages and with only moderate loss in the parameters.