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