I'm havingGiven a hard time explaining my problem, therefore, I've drawn an example directed graph, as you can see below. The edges are annotated with colours. Those colours/annotations would be the output of the process. The input would be the graph without coloured edges. The circle on the left is the starting$G$ and a start vertex, the filled circle on the right is the $s$ and an end vertex.
The goal is to find sets of edges. Each edge in $e$, consider a set has thecoloring of the following property:edges valid if one edge is visited as a part of a possible, for every path from (from start$s$ to end) through the directed graph$e$ and every color $c$, iteither $c$ is guaranteednever encountered along that all other edges in this set will be visited as well. For example, the green edges are greenpath, because if the first greenor every edge that is visited, itcolored $c$ is guaranteed that all other green edges will be visited as well. Same goes for all coloursby that path.
What algorithm could achieve suchGiven $G,s,e$, I would like to find a valid coloring that uses the minimal number of colors. Is there an annotationefficient algorithm for this problem?
A test forI show below an example graph and a potential set would be checking all possible paths fromsample solution. The circle on the left is the starting vertex to, the end vertex and finding no path that just contains a subset offilled circle on the proposed set.
I feel like I'm missingright is the obvious solutionend vertex. Could anyone please help?