Search papers, labs, and topics across Lattice.
This paper adapts the state-of-the-art distributed triangle-free coloring algorithm by Pettie and Su, leveraging a resilient version of the Lov谩sz Local Lemma (LLL) to significantly reduce the complexity of solving LLL instances. The authors achieve an $O(k) + \log^{O(1)}\log n$ round complexity, effectively removing the LLL as a bottleneck when $k = \log^{\omega(1)}\log n$. As a result, they present the first algorithms capable of coloring triangle-free graphs with $o(\Delta)$ colors in $\log^{O(1)}\log n$ rounds, along with a companion algorithm for girth-5 graphs that matches existing upper bounds on color usage.
Achieving triangle-free graph coloring in $\log^{O(1)}\log n$ rounds could redefine the efficiency benchmarks for distributed algorithms in sparse graph structures.
The Lov\'asz Local Lemma (LLL) is a probabilistic tool that has been shown to be of central importance in the study of distributed algorithms. For example, the constructive LLL is known to be complete for the class of locally-checkable labeling problems with $o(\log n)$ randomized complexities in the LOCAL model. One classic application of the LLL is in coloring graphs with some sparse structure, such as triangle-free graphs. Triangle-free coloring therefore serves as a benchmark problem for techniques for sublogarithmic randomized distributed algorithms. The state-of-the-art distributed triangle-free coloring algorithm of Pettie and Su [ICALP 2013, Information and Computation 2015] uses $\frac{\Delta}{k}$ colors (where $k$ can be up to $(\frac14 - \varepsilon)\ln \Delta$) and consists of $O(k+\log^* n)$ applications of the distributed LLL. However, the distributed LLL is itself a difficult problem; despite significant study, the fastest algorithms known require $O(\log_\Delta n)$ or $O(\frac{\Delta}{\log\Delta})+\log^{O(1)}\log n$ rounds. In this work, we adapt the Pettie-Su's algorithm so that the resulting LLL instances can be solved in $\log^{O(1)}\log n$ rounds, by employing the'resilience'definition of Davies [SODA 2023]. This gives an $O(k)+ \log^{O(1)}\log n$ complexity (since the LLL is not needed when $k= \log^{\omega(1)}\log n$), essentially causing the LLL steps to no longer be the bottleneck of the algorithm. As a corollary we obtain the first $\log^{O(1)}\log n$-round algorithms for coloring triangle-free graphs with $o(\Delta)$ colors. The same framework also yields a companion girth-$5$ algorithm, using $(1+\varepsilon)\Delta/\ln \Delta$ colors in $O(k)+ \log^{O(1)}\log n$ rounds, matching the best known existential upper bound for the number of colors.
