Take the 2-minute tour ×
Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It's 100% free, no registration required.

I have the following problem:

Given an edge-colored DAG $G = (V,A)$, vertices $s$ and $t$, a set of colors $C$ and $k \in \mathbb{N}$,
does there exist a path from $s$ to $t$ using exactly $k$ distinct colors?

Can anyone provide pointers to the complexity of this problem? More specific, is it $\mathsf{NP}$-complete or in $\mathsf{P}$?

share|improve this question
3  
You may first ask the existence of such a path, and it should not be difficult to show that the problem is NP-complete by a reduction of CNF-SAT. –  Yoshio Okamoto Feb 1 '13 at 11:35
    
I had few doubts about its NP-completeness while I'm more interested in possible approximation algorithms. Of course, it was my mistake that I did not mention it. –  user547616 Feb 1 '13 at 12:08
3  
Then, please edit your question accordingly. –  Yoshio Okamoto Feb 1 '13 at 13:48
    
@YoshioOkamoto Could you sketch the reduction? I can't think of how to do it. –  G. Bach Feb 2 '13 at 14:11
    
@G.Bach: Since it was too long to be a comment, I sketched the reduction as an answer. –  Yoshio Okamoto Feb 3 '13 at 4:20
add comment

migrated from cstheory.stackexchange.com Feb 4 '13 at 20:42

This question came from our site for theoretical computer scientists and researchers in related fields.

1 Answer

Here is a reduction of CNF-SAT.

In a given CNF formula, assume we have variables $x_1, \dots, x_n$ and clauses $C_1, \dots, C_m$.

We construct a DAG with edge colors as follows.

We have $m$ colors, and each color corresponds to a clause. In our DAG, we have vertices $v_0$, $v_1$, ..., $v_n$, and $v_0$ is the source and $v_n$ is the sink. (There will be more vertices in our DAG.)

From $v_{i-1}$ to $v_{i}$, we have a pair of vertex-disjoint paths (you may think they are parallel), one for TRUE and one for FALSE corresponding to the assignment to $x_i$. On the path for TRUE, we have edges with the colors corresponding to the clauses with $x_i$ appearing as positive literals. On the path for FALSE, we have edges with the colors corresponding to the clauses with $x_i$ appearing as negative literals.

A path exists from $v_0$ to $v_n$ with $m$ colors if and only if the given formula is satisfiable.

share|improve this answer
    
Thanks! That clarified it for me. –  G. Bach Feb 3 '13 at 4:51
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.