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