I know Distributed Graph Coloring algorithm in O(log* n) which is given at P11: Vertex Coloring

Same for Maximal Independent Set [MIS] they gave remark like algorithms exist in O(log* n) time at P70: Maximal Independetn Set

How we can reduce Graph coloring problem to MIS in O(log* n) time?


A tree is always a bipartite graph, which means it will have only two colors.

Look at what the algorithm described on the paper you have linked:

We first choose all nodes of the first color. Then, for each additional color
we add "in parallel" (without conflict) as many nodes as possible.

Being bicolored means that if you choose any of the two colors, no nodes from the other color can be added. So, for a Tree, finding the MIS has time complexity equal to the coloring algorithm (just color it, then the color with most nodes is the MIS, that can be chosen in constant time).

If you can color in $O(\log^* n)$, then that's $O(\log^* n)$ for a tree (that, however, is only for graphs that can be bicolored).

Regarding your specific confusion:

Any graph that is $N$-colorable is also $M$-colorable with $M > N$ and $M \leq V$ (number of vertices). This doesn't change the fact that a tree is bipartite (meaning it is 2-colorable). To see this, just take a bicolored graph. To create a third color, you can just color any node with a third color (or as many as you want, as long as they had the same previous color).

Now, I don't have much knowledge about distributed algorithms, but the paper you linked on the comment says that 3-coloring the tree is actually less expensive than 2-coloring it (regarding the amount of messages sent). This doesn't change the fact that, for a tree, you can be sure that it is $N$-colorable (with $N \geq 2$ and $N \leq V$).

Now, from Theorem 1.17, you have an algorithm that colors a tree with 3 colors in $O(\log^* n)$. From Corollary 7.3 you have that MIS can be done in time $C + T$.

From what I understand, for a general graph you don't know how many colors it needs, but for a tree, since you know it is $N$-colorable with $N \geq 2$ and can be 3-colored in $O(\log^* n)$, this would give you time $O(3 + \log^* n) = O(\log^* n)$. The difference to a general graph is that the number of colors become constant.

| cite | improve this answer | |
  • $\begingroup$ Tree Coloring using 3 Colors is possible in O(log* n) from that i want MIS algorithm, Please check Page 11: Theorem 1.17, i am talking about that algorithm. $\endgroup$ – Manish Kumar May 4 '14 at 4:06
  • $\begingroup$ I edited my answer trying to address your comment. Hope this helps :) $\endgroup$ – Alvaro May 5 '14 at 2:52
  • $\begingroup$ you want to say: O(log n)= O(log* n) ? $\endgroup$ – Manish Kumar May 5 '14 at 16:16
  • $\begingroup$ Yes, edited that too $\endgroup$ – Alvaro May 9 '14 at 21:15

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.