# Connected Components over Graph with “colored” edges.

We have an undirected graph $G(V,E)$. Each edge $e \in E$ is associated with a set $C_{e}\neq \emptyset$ of colors, $C_{e} \subseteq C$. The problem is to find all the colored connected components. For example if we have $C=\{\;\mathrm{red},\;\mathrm{black},\;\mathrm{yellow}\}$. The Red connected components are all the connected components considering only the edges that contains red in the color set. Now a naive algorithm is to do the normal search for each $c\in C$. The cost seems to be $O(|C|(|V|+|E|))$. The question is: is it possible to do better?

• I don't think it can be done faster than solving $|C|$ connected component problems (direct sum), but I don't know if what you described is the best way to do it. – Kaveh Aug 4 '11 at 14:57
• I agree with Kaveh. How would it be any easier than doing the work for $|C|$ graphs on the same number of vertices? – Andrew D. King Aug 4 '11 at 17:07