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?

Improve this question
$\endgroup$

1 Answer 1

Reset to default
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.

Improve this answer
$\endgroup$
7
  • $\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
    Commented Aug 27, 2018 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
    Commented Aug 27, 2018 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
    Commented Aug 27, 2018 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
    Commented Aug 27, 2018 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
    Commented Aug 27, 2018 at 9:50

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.