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. enter image description here

  • $\begingroup$ 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. $\endgroup$ Mar 12 at 3:35
  • $\begingroup$ 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? $\endgroup$ Mar 12 at 3:58
  • $\begingroup$ 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 $\endgroup$ Mar 12 at 4:01
  • $\begingroup$ 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? $\endgroup$
    – D.W.
    Mar 12 at 11:15
  • $\begingroup$ 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. $\endgroup$ 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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.