# Determine if there is a path with alternating edge colours in directed graph

Given directed graph $$G = \langle V, E \rangle$$, such that some vertices are red, and some vertices are black, and some edges are blue or green, decide for all vertices $$v \in V$$ if there is path from $$v$$ to some red vertex with alternating edge colours (no edges of same colour are adjacent in the path, e.g. blue -> green -> blue -> ...).

If $$G$$ is acyclic, the problem looks simple - just use DFS. But how can one solve it if there are cycles in $$G$$?

• Why do the presence of cycles bother you? I mean, DFS (aka Depth-First Search) is indeed the algorithm of choice for detecting them ... This problem is solved with a straightforward application of Depth-First search indeed – Carlos Linares López Mar 10 at 16:34

Let's construct a new graph $$G'$$.

Every vertex $$u$$ from $$G$$ will become a pair of vertexes in $$G'$$, namely $$u_{blue}$$ and $$u_{green}$$ (index stands for the color of incoming edge).

Edge $$u_{c_1}\rightarrow w_{c_2}$$ in $$G'$$ exists iff

1. There is an edge $$u \rightarrow w$$ in $$G$$ colored $$c_2$$
2. $$c_1 \ne c_2$$

Now it's easy to see that every path in $$G'$$ corresponds to a color-alternating path in $$G$$ (and the converse is also true), i.e. color-alternating path from $$v$$ to $$u$$ in $$G$$ exists iff there is path from $$v_{c_1}$$ to $$u_{c_2}$$ in $$G'$$ for some $$c_1, c_2$$.

• What do you mean by "start vertex"? For example, if $G$ is a cycle of length 4, what vertex will be the "start" one? – alex07021998 Mar 9 at 19:11
• @alex07021998 I misread the question. See the update. – Vladislav Mar 9 at 19:19