2016/07/18 by Dan Hefetz, Fabian Kühn, Hefetz, Dan +5 · 1 citation
Computer Science · #Complexity and Algorithms in Graphs #Distributed #FOS: Computer and information sciences #Optimization and Search Problems #Parallel #Privacy-Preserving Technologies in Data #and Cluster Computing (cs.DC)
paper · pdf · doi:10.48550/arxiv.1607.05212
openalex publication_date 2016/07/18 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
We show an Ω(Δ^(1)/(3)-\fracη3) lower bound on the runtime of any deterministic distributed O(Δ1+η)-graph coloring algorithm in a weak variant of the \LOCAL model. In particular, given a network graph G=(V,E), in the weak \LOCAL model nodes communicate in synchronous rounds and they can use unbounded local computation. We assume that the nodes have no identifiers, but that instead, the computation starts with an initial valid vertex coloring. A node can broadcast a single message of unbounded size to its neighbors and receives the set of messages sent to it by its neighbors. That is, if two neighbors of a node v∈ V send the same message to v, v will receive this message only a single time; without any further knowledge, v cannot know whether a received message was sent by only one or more than one neighbor. Neighborhood graphs have been essential in the proof of lower bounds for distributed coloring algorithms, e.g., \citelinial92,Kuhn2006On. Our proof analyzes the recursive structure of the neighborhood graph of the respective model to devise an Ω(Δ^(1)/(3)-\fracη3) lower bound on the runtime for any deterministic distributed O(Δ1+η)-graph coloring algorithm. Furthermore, we hope that the proof technique improves the understanding of neighborhood graphs in general and that it will help towards finding a lower (runtime) bound for distributed graph coloring in the standard \LOCAL model. Our proof technique works for one-round algorithms in the standard \LOCAL model and provides a simpler and more intuitive proof for an existing Ω(Δ2) lower bound.