1
$\begingroup$

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$?

Improve this question
$\endgroup$
1
  • $\begingroup$ 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 $\endgroup$ – Carlos Linares López Mar 10 '20 at 16:34
1
$\begingroup$

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$.

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

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.