#StackBounty: #algorithms #graphs #colorings #topological-ordering How to edge-color a directed acyclic graph so that every path visits…

Bounty: 100

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.

Get this bounty!!!

This site uses Akismet to reduce spam. Learn how your comment data is processed.