2023/12/03 by Yi‐Jun Chang, Gopinath Mishra, Chang, Yi-Jun +7 · 2 citations
Computer Science · #Data Structures and Algorithms (cs.DS) #Distributed #FOS: Computer and information sciences #Optimization and Search Problems #Parallel #and Cluster Computing (cs.DC)
paper · pdf · doi:10.48550/arxiv.2312.01384
openalex publication_date 2023/12/03 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Recently, \citeauthor*akbari2021locality~(ICALP 2023) studied the locality of graph problems in distributed, sequential, dynamic, and online settings from a unified point of view. They designed a novel O(log n)-locality deterministic algorithm for proper 3-coloring bipartite graphs in the Online-LOCAL model. In this work, we establish the optimality of the algorithm by showing a tight deterministic Ω(log n) locality lower bound, which holds even on grids. To complement this result, we have the following additional results: \beginenumerate \item We show a higher and tight Ω(√(n)) lower bound for 3-coloring toroidal and cylindrical grids. \item Considering the generalization of 3-coloring bipartite graphs to (k+1)-coloring k-partite graphs, %where k ≥ 2 is a constant, we show that the problem also has O(log n) locality when the input is a k-partite graph that admits a locally inferable unique coloring. This special class of k-partite graphs covers several fundamental graph classes such as k-trees and triangular grids. Moreover, for this special class of graphs, we show a tight Ω(log n) locality lower bound. \item For general k-partite graphs with k ≥ 3, we prove that the problem of (2k-2)-coloring k-partite graphs exhibits a locality of Ω(n) in the \onlineLOCAL model, matching the round complexity of the same problem in the \LOCAL model recently shown by \citeauthor*coiteux2023no~(STOC 2024). Consequently, the problem of (k+1)-coloring k-partite graphs admits a locality lower bound of Ω(n) when k≥ 3, contrasting sharply with the Θ(log n) locality for the case of k=2. \endenumerate