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

  • 3
    $\begingroup$ 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. $\endgroup$
    – Yoshio Okamoto
    Feb 1 '13 at 11:35
  • $\begingroup$ 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. $\endgroup$
    – user547616
    Feb 1 '13 at 12:08
  • 3
    $\begingroup$ Then, please edit your question accordingly. $\endgroup$
    – Yoshio Okamoto
    Feb 1 '13 at 13:48
  • $\begingroup$ @YoshioOkamoto Could you sketch the reduction? I can't think of how to do it. $\endgroup$
    – G. Bach
    Feb 2 '13 at 14:11
  • $\begingroup$ @G.Bach: Since it was too long to be a comment, I sketched the reduction as an answer. $\endgroup$
    – Yoshio Okamoto
    Feb 3 '13 at 4:20

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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy