Mixing
![Third party employment : Good or Bad [closed]](https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEgjbpfN9tAutmK93bJRC3ZoROZzi2TJDms5n8_qJuhgE0a9b52OOHayv3NGT8igAdFL7byXNst-_1DZK5SjrIJ28_6RQPUpBROqMs5s6jo-ZsjX8kjDwfxJufIitH3TaQRXWaGSQKRQib-f/s72-c/1.jpg)
A directed graph colored path problem?
Clash Royale CLAN TAG#URR8PPP
up vote
0
down vote
favorite
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?
algorithms complexity-theory graph-theory np
asked Aug 27 at 7:40
J.Doe
1906
add a comment |Â
up vote
0
down vote
favorite
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?
algorithms complexity-theory graph-theory np
asked Aug 27 at 7:40
J.Doe
1906
add a comment |Â
up vote
0
down vote
favorite
up vote
0
down vote
favorite
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?
algorithms complexity-theory graph-theory np
asked Aug 27 at 7:40
J.Doe
1906
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?
algorithms complexity-theory graph-theory np
asked Aug 27 at 7:40
J.Doe
1906
asked Aug 27 at 7:40
J.Doe
1906
asked Aug 27 at 7:40
J.Doe
1906
asked Aug 27 at 7:40
J.Doe
1906
1906
add a comment |Â
add a comment |Â
1 Answer
1
active
oldest
votes
up vote
2
down vote
accepted
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.
answered Aug 27 at 8:00
Peter Taylor
640310
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)
– Taemyr
Aug 27 at 9:04
1
@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 at 9:38
Even if N≤|V| you are still outside of polynomial time. Input size for N is O(log N) - hence the requirement for unary.
– Taemyr
Aug 27 at 9:41
1
@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 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 at 9:50
 |Â
show 2 more comments
1 Answer
1
active
oldest
votes
1 Answer
1
active
oldest
votes
active
oldest
votes
active
oldest
votes
up vote
2
down vote
accepted
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.
answered Aug 27 at 8:00
Peter Taylor
640310
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)
– Taemyr
Aug 27 at 9:04
1
@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 at 9:38
Even if N≤|V| you are still outside of polynomial time. Input size for N is O(log N) - hence the requirement for unary.
– Taemyr
Aug 27 at 9:41
1
@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 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 at 9:50
 |Â
show 2 more comments
up vote
2
down vote
accepted
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.
answered Aug 27 at 8:00
Peter Taylor
640310
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)
– Taemyr
Aug 27 at 9:04
1
@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 at 9:38
Even if N≤|V| you are still outside of polynomial time. Input size for N is O(log N) - hence the requirement for unary.
– Taemyr
Aug 27 at 9:41
1
@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 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 at 9:50
 |Â
show 2 more comments
up vote
2
down vote
accepted
up vote
2
down vote
accepted
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.
answered Aug 27 at 8:00
Peter Taylor
640310
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.
answered Aug 27 at 8:00
Peter Taylor
640310
answered Aug 27 at 8:00
Peter Taylor
640310
answered Aug 27 at 8:00
Peter Taylor
640310
answered Aug 27 at 8:00
Peter Taylor
640310
640310
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)
– Taemyr
Aug 27 at 9:04
1
@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 at 9:38
Even if N≤|V| you are still outside of polynomial time. Input size for N is O(log N) - hence the requirement for unary.
– Taemyr
Aug 27 at 9:41
1
@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 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 at 9:50
 |Â
show 2 more comments
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)
– Taemyr
Aug 27 at 9:04
1
@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 at 9:38
Even if N≤|V| you are still outside of polynomial time. Input size for N is O(log N) - hence the requirement for unary.
– Taemyr
Aug 27 at 9:41
1
@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 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 at 9:50
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)
– Taemyr
Aug 27 at 9:04
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)
– Taemyr
Aug 27 at 9:04
1
1
@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 at 9:38
@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 at 9:38
Even if N≤|V| you are still outside of polynomial time. Input size for N is O(log N) - hence the requirement for unary.
– Taemyr
Aug 27 at 9:41
Even if N≤|V| you are still outside of polynomial time. Input size for N is O(log N) - hence the requirement for unary.
– Taemyr
Aug 27 at 9:41
1
1
@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 at 9:43
@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 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 at 9:50
@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 at 9:50
 |Â
show 2 more comments
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fcs.stackexchange.com%2fquestions%2f96660%2fa-directed-graph-colored-path-problem%23new-answer', 'question_page');
);
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
