# edge coloring a directed acyclic graph

I have an edge coloring problem as follows: Suppose we have a DAG which has a source vertex s and an end vertex e, in addition, all the paths from s to e are of the same length say L. We define L colors from 1 to L. Is there an efficient edge coloring algorithm to color all the edges, such that every path from s to e uses all the L colors and every path must be labeled differently? I attach a picture below for illustration, where vertex 1 is s, vertex 10 is e.

• There could be more than $L!$ paths, in which case no such edge colouring exists. Restricting to instances with solutions, a simple observation: All subpaths between two vertices must have the same length and must be coloured with permutations of the same subset of colours. Mar 12 at 3:35
• Thanks for the reply. L! paths indeed, and the solution is not unique. But my question: is there a systematic way to find one of possible solutions? Mar 12 at 3:58
• The solution needs to satisfy your observation: All subpaths between two vertices must have the same length and must be coloured with permutations of the same subset of colours Mar 12 at 4:01
• Can you tell us the motivation or the context where you encountered this task? Was this an exercise in a textbook or class? If so, what have you been studying most recently? Is it a practical problem? If so, how large will $L$ be in practice?
– D.W.
Mar 12 at 11:15
• I have this problem from a research project. Generally, L is between 3 and 10. The number of paths between s and e is smaller than L!. While there might be multiple solutions for a given graph, only one is wanted as long as it satisfies the requirements. Mar 12 at 14:04

I don't know whether there is a polynomial-time solution. Since $$L$$ is fairly small ($$L\le 10$$), one possible approach is to use a SAT solver.

Suppose $$L=10$$. For each vertex $$v_5$$ at distance 5 from $$s$$, we'll enforce that all paths $$s \leadsto v_5$$ have a different color sequence. Then, we'll do the same for all paths $$v_5 \leadsto e$$. This suffices to ensure your property holds. (In general, replace 5 with $$L/2$$.)

Here is a plausible way to encode this in SAT. For each edge $$e$$ and each color $$c$$, add a boolean variable $$x_{e,c}$$, which captures whether edge $$e$$ is assigned color $$c$$. Also, for each pair of edges $$e,e'$$ at the "same level" (i.e., their start nodes are at the same distance from $$s$$), and for each pair of edges $$e,e'$$ that are part of the same path from $$s$$ to some vertex at distance 5 or some path from a vertex at distance 5 to $$e$$, add a boolean variable $$y_{e,e'}$$, which captures whether $$e,e'$$ receive the same color. Then add constraints:

• Enforce that $$y$$ are transitive by adding $$y_{e,e'} \land y_{e',e''} \implies y_{e,e''}$$.

• Enforce that $$x,y$$ are consistent by adding $$y_{e,e'} \land x_{e,c} \implies x_{e',c}$$ and $$x_{e,c} \land x_{e',c} \implies y_{e,e'}$$.

• Enforce that the $$x$$'s are a one-hot encoding by adding the constraints $$\bigvee_c x_{e,c}$$ and $$\neg x_{e,c} \lor \neg x_{e,c'}$$ for all $$e,c,c'$$.

• Enforce that each path uses all colors, by requiring $$\neg y_{e,e'}$$ for all pairs of edges $$e,e'$$ in the same path.

• Enforce that each path uses different colors: for each pair of paths of the form $$s \to v_1 \to v_2 \to v_3 \to v_4 \to v_5$$, $$s \to v'_1 \to v'_2 \to v'_3 \to v'_4 \to v_5$$, add the constraint $$y_{s\to v_1,s\to v'_1} \lor y_{v_1\to v_2,v'_1\to v'_2} \lor \dots \lor y_{v_4 \to v_5,v'_4 \to v_5}.$$ Do the same for each pair of paths of the form $$v_5 \leadsto e$$.

Then use an off-the-shelf SAT solver to solve this SAT instance.

I think the number of variables and clauses won't grow too large, so maybe there is a hope this instance of SAT might be solvable in a reasonable amount of time. In particular, for any particular vertex $$v_5$$, the number of paths of the form $$s \leadsto v_5$$ will be at most $$5!=120$$; if there are more, then the graph cannot be colored. Why? Well, as j_random_hacker points out, all such paths must use the same set of 5 colors. So, each such path's color sequence is of the $$5!$$ permutations of that set. Also, each such path must have a different color sequence (otherwise we can pick any one path $$v_5 \leadsto e$$, append it to both, and obtain two paths $$s \leadsto e$$ with the same color sequence), so there can be at most $$5!$$ such paths. This means that the SAT instance will have something like $${120 \choose 2} M + {M \choose 2}$$ boolean variables and clauses, where $$M$$ is the max number of vertices per layer.