# Path on an edge-colored DAG using exactly $k$ colors

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}$?

• 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
– Yoshio Okamoto
Feb 1 '13 at 13:48
• @YoshioOkamoto Could you sketch the reduction? I can't think of how to do it. 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

In a given CNF formula, assume we have variables $x_1, \dots, x_n$ and clauses $C_1, \dots, C_m$.
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.