A directed graph colored path problem?

Question

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.

Can someone please help with this?

Answer 1

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: the first algorithm only seems polynomial if the colours are given in unary. (Although OP asks for a specific colour so that would still be polynomial)
• Peter Taylor: @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.
• Taemyr: Even if N≤|V| you are still outside of polynomial time. Input size for N is O(log N) - hence the requirement for unary.
• Peter Taylor: @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|)$).
• Giacomo Alzetta: @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.