Given a directed acyclic graph $G$ and a start vertex $s$ and an end vertex $e$, consider a coloring of the edges *valid* if, for every path from $s$ to $e$ and every color $c$, either $c$ is never encountered along that path, or every edge that is colored $c$ is visited by that path. Given $G,s,e$, I would like to find a valid coloring that uses the minimal number of colors. Is there an efficient algorithm for this problem? I show below an example graph and a sample solution. The circle on the left is the starting vertex, the filled circle on the right is the end vertex. [![Example Graph][1]][1] [1]: https://i.sstatic.net/F8R2P.png