Reminder: This post contains 4173 words
· 12 min read
· by Xianbin
This post revisits the basics on distributed coloring.
\((\Delta+1)\)-coloring
\(\textbf{Theorem}\)[Linial’s coloring] There exists a deterministic distributed algorithm in the \(\textbf{LOCAL}\) model that colors any \(n\)-node graph with maximum degree \(\Delta\) with \(O(\Delta^2)\) colors, in \(O(\log ^*n)\) rounds.
\(\textbf{Proof}\).
To prove this theorem, we need a reduction method.
\(\textbf{Lemma}\)[Reduction Lemma]. Given a \(k_1\)-coloring \(\phi_1\) in a single rounds, we can compute \(k_2\)-coloring \(\phi_2\) for \(k_2 = O(\Delta^2 \log k_1)\). If \(k_1 \leq \Delta^3\), we obtain \(k_2 = O(\Delta^2)\).
We start with the initial numbering of the vertices as a trivial \(n\)-coloring. By applying the reduction lemma, we obtain a \(O(\Delta^2\log n)\) coloring. Then, after each iteration, we will obtain \(O(\Delta^2(\log \Delta + \log \log n)), O(\Delta^2(\log \Delta + \log \log \log n)), \cdots\). After repeating \(O(\log^*n)\) iterations, we obtain a \(O(\Delta^2 \log \Delta)\) coloring (by the definition of \(\log ^*n\)). Then by the second part of the reduction lemma, we obtain an \(O(\Delta^2)\)-coloring.
Proof of the Reduction Lemma (part 1)
\(\textbf{Definition}\)[Cover Free Families]. Given a universe set \(\{1,2,\ldots, k_1\}\), a family set \(S_0,S_1,\ldots,S_{k} \subseteq \{1,2,\ldots,k_1\}\) is called \(\Delta\)-cover free family if for each set of indices \(i_0,i_1,\ldots,i_\Delta \in \{1,2,\ldots,k\}\), we have
\(S_{i_0} \setminus \left(\bigcup_{j=1}^\Delta S_{i_j} \right)\not = \emptyset\)
That is to say, none of the set in the family is a subset of the union of \(\Delta\) other sets.
If such a cover family exists (actually \(k_1 = O(\Delta^2\log \Delta)\) is enough), we can easily find a \(k_1\)-coloring. Each node \(u\) has \(S_i\), and only needs to collect the indices of \(S_j\) of other \(\Delta\) neighbors. Node selects any color in the set \(S_{i}\setminus \bigcup S_j\).
So, we only need to prove such a \(\Delta\)-cover free family exists.
\(\textbf{Lemma}\)[Existence of Cover Free Families]. For any \(k, \Delta\), there exists a \(\Delta\)-cover free family of size \(k\) on a universe set of size \(k_1 = O(\Delta^2 \log k)\).
\(\textbf{Proof}\). It is not hard to think of using the probabilistic method to find such a family set.
The process is as follows. Let \(k_1 = C\Delta^2 \log k\) where \(C\) is a large enough positive constant. For each \(i\in[k]\), we define each set \(S_i \subset \{1,2,\ldots,k_1\}\) by including each element \(e\in \{1,2,\ldots,k_1\}\) in \(S_i\) with probability \(1/\Delta\). We will prove that this random construction will output a \(\Delta\)-cover free family with high probability.
Consider an arbitrary set of indices \(i_0, \ldots, i_\Delta\in \{1, \ldots, k\}\).
For any element \(e \in \{1,\ldots,C\Delta^2 \log k\}\), the probability that there is an element \(e\) in \(S_{i_0}\setminus \bigcup S_{i_j}\) is \(1/\Delta \cdot (1-1/\Delta)^{\Delta} \leq 1/(4\Delta)\). Then, the probability that there is no such elements in \(S_{i_0}\setminus \bigcup S_{i_j}\) is
\[(1-1/(4\Delta))^{\Delta^2 \log k} \leq e^{\frac{-C\Delta \log k}{4}}\]
Recall that we need to prove that for each set of indices, \(\Delta\)-cover free family exists.
There are \(k {\Delta \choose k-1}\) ways to choose a set of indices.
Let \(E_1\) denote the construction fails. By the union bound over all choices.
\[P[E_1] \leq \sum_{i=1}^{k {\Delta \choose k-1}} e^{\frac{-C\Delta \log k}{4}}\leq \sum_{i=1}^{k {\Delta^{k-1}}}e^{\frac{-C\Delta \log k}{4}} = e^{\log k+\Delta \log (k-1) - \frac{C\Delta\log k}{4}} \ll 1\]
Proof of the Reduction Lemma (part 2)
\(\textbf{Lemma}\). For any \(k\) and \(k \leq \Delta^3\), there exists a \(\Delta\)-cover free family of size \(k\) on a universe set of size \(k_1 = O(\Delta^2)\).
\(\textbf{Proof}\). This can be done by low-degree polynomials.
From \(O(\Delta^2)\)-coloring to \((\Delta+1)\)-coloring
The basic idea is very simple. We reduce one color for each time, and after \(O(\Delta^2)\) rounds, we can obtain an \((\Delta+1)\)-coloring.
\(\textbf{Lemma}\) Given a \(k\)-coloring \(\Phi_1\) of a graph with maximum degree \(\Delta\) and \(k\leq \Delta+2\), in a single round, we can compute a \((k-1)\)-coloring \(\Phi_2\).
The proof is simple. For each node \(u\), if \(\phi_1(u) = k\), we replace it with one of the color \(\{1,\ldots,\Delta+1\}\).
Therefore, there exists a distributed algorithm for \((\Delta+1)\)-coloring in the LOCAL model within \(O(\Delta^2 + \log^* n)\) rounds.
Parallelize the Reducing Method
\(\textbf{Lemma}\) Given a \(k\)-coloring \(\Phi_1\) of a graph with maximum degree \(\Delta\) and \(k\geq \Delta+2\), in a \(O(\Delta \log (k/(\Delta+1)))\) rounds, we can compute a \((\Delta+1)\)-coloring \(\Phi_2\).
(TO DO Later).
Reference
[1]. Distributed Graph Algorithms. Mohsen Ghaffari.