# A directed graph colored path problem?

Given: A rooted, directed, a-cyclic graph $G$. Let $r_0$ be the root node and $t_0$ be another target node. Each node in $G$ is assigned a non unique id/color ($ID_i),\ 1<i<N$ for some integer N.

Problem: Is there a directed path from $r_0$ to $t_0$, such that for some $ID_x$ there is no node in that path with $ID_x$ as its $ID$. In other words, the nodes in the path do-not cover all the $IDs$.

Comments: Clearly the problem is in $NP$ since if we are given such a path we can easily verify it. I suspect the problem is also in $P$ and can be solved in polynomial time. But, I am struggling to find an algorithm for the same.

Simple approach: for each $1 \le i \le N$ (I assume that the $<$ in the question are typos) run depth-first or breadth-first search ignoring nodes coloured $i$.
Slightly more advanced approach: use a matrix-based all-pairs reachability algorithm, but rather than record a Boolean isReachable or a numeric shortestDistance record a bitmap of which colours can be avoided.
• @Taemyr, yes-ish. IMO it's a reasonable assumption that $N \le |V|$, but I concede that this isn't explicit in the question or the answer. – Peter Taylor Aug 27 '18 at 9:38
• @Taemyr, I'm also assuming that $G$ is encoded in the input, since otherwise there are very few graph algorithms which are poly-time. (Or even if $G$ isn't, if the colouring is then it's $\Omega(N|V|)$). – Peter Taylor Aug 27 '18 at 9:43
• @Taemyr If we want to take all considerations then $N$ could also simply be a costant and so does not affect the complexity of the algorithm... the OP did not specify whether he has a "concrete problem" in mind which is modelled by this graph and this could have implications on the range of $N$ or whether or not it should be considered constant. – Giacomo Alzetta Aug 27 '18 at 9:50