The Pettie-Su's algorithm is adapted 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].
Abstract
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.
The first $poly(\Delta,\log n)-round algorithm for $(\Delta + 1)$-edge coloring in the CONGEST model is presented and the $n$-dependency of its runtime, $\tilde{O}(\log^5 n)$, matches the best published dependency in the LOCAL model.
Sebastian Brandt, Ananth Narayanan, Alexandre Nolin· 0 citations
This work generalizes and combines tools from the $(k+2)-coloring to $k$-list-coloring reduction of [Zamir, ICALP 2021] and the hypergraph-containers based approach in [Zamir, STOC 2023] and yields an iterable reduction from $(k+1)$-list-coloring to $k$-list-coloring over fixed palettes.
We show that the complexity gaps in the round complexities of locally checkable labeling (LCL) problems are not due to the fact that solutions to LCL problems must be locally checkable, but solely to the fact that LCL problems are defined only for graphs of maximum degree upper bounded by some arbitrary yet constant value $\Delta$. Specifically, we show that there are infinitely many locally checkable problems (i.e., problems whose solutions can be checked locally) whose round complexities belongs to the two intervals $[\omega(1),o(\log\log^\star n)]$ and $[\omega(\log^\star n),o(\log n)]$ whenever these problems are considered in networks with unbounded maximum degrees. This extends the previous results by Schmid (arXiv, 2026), which hold for the polynomial regime only, and by Bousquet, Feuilloley, and Pierron (OPODIS, 2025), which hold for trees only. All our upper bounds are obtained using deterministic algorithms that can be run under the port-numbering model, which is a weak variant of LOCAL, without any a priori information on the number of nodes in the network. Instead, our lower bounds apply to randomized LOCAL, and quantum LOCAL, even if nodes have identifiers in $[1,n]$, and even if they know the exact number of nodes in the network. They even hold under randomized online LOCAL, a strong variant of the LOCAL model. Finally, our lower bounds hold even for trees. Our results are obtained using two main ingredients. The first one is the analysis of a new locally checkable problem called Increasing Degree, parameterized by a function $f:\mathbb{N}\to\mathbb{N}$. Different round complexities can be obtained by tuning the function $f$ accordingly. Our second tool is a general Translation Theorem that enables to transfer results from a given range of complexities to results for a range of lower complexities.
Filippo Casagrande, Pierre Fraigniaud, Benjamín Jauregui et al.· 0 citations
It is proved that if the number of colors $c$ is not a perfect square, the state-of-the-art defect for distributed $c-colorings by a constant factor in most cases can be improved.
A suite of fast randomized distributed algorithms representing varying points on this tradeoff are presented, analyze their properties, and study their time complexity in the sequential, CONGEST and Congested Clique models.
For every $\varepsilon>0$, it is NP-hard to $n^{1-\varepsilon}$-approximate Max Independent Set in $n$-vertex graphs [Hastad'96, Zuckerman'07]. In triangle-free graphs, a simple argument gives a polynomial-time $n^{1/2}$-approximation algorithm, whereas, for every $\varepsilon>0$, an $n^{1/4-\varepsilon}$-approximation algorithm would imply that NP $\subseteq$ BPP [Bonnet, Thomass\'e, Tran, Watrigant; ESA'20]. In this note, we close this gap by proving the corresponding hardness against $n^{1/2-\varepsilon}$-approximation algorithms. The reduction is very simple and uses the Moser-Tardos resampling algorithm to make the constructed graphs triangle-free. The soundness uses a result of Haeupler, Saha, and Srinivasan building on the proof of Moser and Tardos, to upper-bound the probability that a fixed relatively large subset is an independent set after the Moser-Tardos algorithm terminates. We generalize this scheme and show that, for any nonempty finite family $\mathcal F$ of graphs, each containing at least one cycle, for any $\varepsilon>0$, an $n^{\mu(\mathcal F)-\varepsilon}$-approximation algorithm for Max Independent Set in graphs excluding every member of $\mathcal F$ as a subgraph implies that NP $\subseteq$ BPP, where $\mu(\mathcal F) := 1 - \max\limits_{H \in \mathcal F}~\min\limits_{U \subseteq V(H), H[U] \text{contains a cycle}} (|U|-2)/(|E(H[U])|-1)$.