0
$\begingroup$

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?

$\endgroup$
2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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) $\endgroup$ – Taemyr Aug 27 '18 at 9:04
  • 1
    $\begingroup$ @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. $\endgroup$ – Peter Taylor Aug 27 '18 at 9:38
  • $\begingroup$ Even if N≤|V| you are still outside of polynomial time. Input size for N is O(log N) - hence the requirement for unary. $\endgroup$ – Taemyr Aug 27 '18 at 9:41
  • 1
    $\begingroup$ @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|)$). $\endgroup$ – Peter Taylor Aug 27 '18 at 9:43
  • $\begingroup$ @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. $\endgroup$ – Giacomo Alzetta Aug 27 '18 at 9:50

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.