edge coloring a directed acyclic graph

Question

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.

Answer 1

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.