6
$\begingroup$

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.

Example Graph

$\endgroup$
  • 1
    $\begingroup$ Just to confirm: all the edges which are not on any s-to-e path can be coloured their own separate colour, even if they may not be connected to each other? $\endgroup$ – JimN Sep 20 at 4:13
  • $\begingroup$ Edges, that aren't on any s-to-e path can be ignored/removed from the graph. They don't matter. $\endgroup$ – Gizmo Sep 20 at 9:41
3
+100
$\begingroup$

You can color a pair of arcs $(a_1,a_2)$ by the same color, if and only if all the paths from the source to the sink, passing through the arc $a_1$, also pass through the arc $a_2$.

Let's consider the set $P$ of all paths from the source to the sink in the graph $G=(V,A)$. Let's denote the subset $P(a) \subset P$ of all paths, passing through the arc $a$. Then we can define an equivalence relation on the set $A$:

$$(a_1 \sim a_2) \equiv (P(a_1) = P(a_2))$$

A minimum number of colors, needed to color all the arcs in the graph $G$ according to your restriction, will be equal to the number of equivalence classes for the relation above.

The algorithm to split all the arcs into such equivalence classes is exact, but may be slow for large graphs. It consists of two steps:

Step 1. For each arc $a \in A$ compute the subset $P(a) \subset P$. This can be done by scanning all the paths in the set $P$, and updating all the subsets $P(a)$ along each such path.

Step 2. Let's assume that we store all the subsets $P(a)$ as binary numbers. Sort the set $A$ by these numbers - this will allow us to group together all the arcs with the same subset of paths. Scan this sorted set of arcs, assigning the same color to arcs in each group.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Great stuff! You inspired me to try to improve your method: cs.stackexchange.com/a/130521/755. $\endgroup$ – D.W. Sep 26 at 7:09
  • 1
    $\begingroup$ $P$ is potentially exponentially sized, though, so storing and sorting $P(a)$ takes potentially quite some time. $\endgroup$ – Pål GD Sep 27 at 19:37
  • $\begingroup$ Your if and only if is essentially the same as my definition of laminar, i.e. $a_1$ in a path if and only if $a_2$ is in the path (for all paths). $\endgroup$ – Pål GD Sep 27 at 19:38
  • $\begingroup$ To be clear, I don't think exponential qualifies as efficient in this case. $\endgroup$ – Pål GD Sep 27 at 19:44
  • $\begingroup$ @PålGD - of course you are right, however please see my another answer for this question. $\endgroup$ – HEKTO Oct 3 at 1:09
3
$\begingroup$

It sounds to me like the greedy algorithm should work, I'm not able to come up with any counter-examples, however, I haven't had time to try to prove the claim either.

Terminology

Definition. Let $s$ be the start and $t$ be the end vertices (source and sink, respectively). Let $a$ and $b$ be vertices where there is a path from $a$ to $b$ (from now on $a < b$), i.e. $s \leq a < b \leq t$. We say that an $st$-path $P = \left(s=v_1, \dots, v_\ell=t\right)$ is $(a,b)$-non-laminar if $a \in P$ and $b \notin P$, or $a \notin P$ and $b \in P$. Intuitively, this means that $P$ "branches" out between $a$ and $b$, and branches in after $b$, or branches out before $a$ and branches in between $a$ and $b$.

Let us define $\text{lca}(v)$ to be the vertex that is the lowest common ancestor of the vertices $\{u \in V \mid (u,v) \in E\}$, i.e. the lowest common ancestor of the in-neighbors of $v$.

We say that a path is $v$-non-laminar if it is $(\text{lca}(v), v)$-non-laminar.

Greedy algorithm.

(1) If a vertex has in-degree = 1 and out-degree = 1, then you use the in-arc's color for the out-arc.

(2) Every time you fan out, that is, whenever you have a vertex with out-degree at least two, each out-arc needs a new color.

(3a) Every time you fan in, i.e., there is a vertex $v$ with in-degree at least two, and there is no $v$-non-laminar path, you take the color of an in-arc of $\text{lca}(v)$.

(3b) Every time you fan in and there is a $v$-non-laminar path, you need a new color.

That should cover all possible cases, and I think it shouldn't be too difficult to show that you can do it in $O(n^2)$ time. It might be possible to lower the time to $O(n + m)$, but I can't think of it now.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ It seems this algorithm assumes every node has out-degree at least 1. $\endgroup$ – xskxzr Sep 27 at 2:22
  • $\begingroup$ Every node that hasn't is irrelevant (except the sink). $\endgroup$ – Pål GD Sep 27 at 8:35
3
$\begingroup$

I present a refinement on HEKTO's algorithm that I think works and should be more efficient: it runs in $O^*(\min(n^3,m^2))$ time.

Theory

Let $P(a)$ denote the set of paths that start at $s$, go through the arc $a$, and end at $e$.

Lemma 1. $a_1,a_2$ can be given the same color iff $P(a_1)=P(a_2)$.

Let $G^*$ be the dual graph of $G$, i.e., each arc of $G$ is a vertex of $G^*$, and for each pair of arcs $u \to v$, $v \to w$ in $G$ we connect the corresponding vertices with a directed arc in $G^*$. The start vertex of $G^*$ is a new vertex $s_0$, and it has an arc in $G^*$ to each arc $s \to v$ in $G$; and similarly for its end vertex.

Lemma 2. An arc $a_2$ is in every path of $P(a_1)$ iff $a_2$ is a dominator or post-dominator of $a_1$ in $G^*$.

Say that $a_1 \prec a_2$ if $a_1$ is the immediate dominator of $a_2$ and $a_2$ is the immediate post-dominator of $a_1$ in $G^*$.

Lemma 3. $P(a)=P(a')$ iff there exists a sequence of arcs $a_1,\dots,a_n$ such that $a=a_1 \prec a_2 \prec \cdots \prec a_n=a'$.

Algorithm

This theory immediately leads to an efficient algorithm for your problem:

  1. Compute the dominator tree $D$ and post-dominator tree $D'$ of $G^*$.

  2. Initialize a Union-Find data structure with each arc of $G$ in its own set.

  3. For arc $a_1$ of $G$, let $a_2$ be its immediate dominator in $D$; if $a_1$ is the immediate dominator of $a_2$ in $D'$, call Union($a_1,a_2$).

  4. Assign a different color to each set of the Union-Find data structure.

Running time analysis

If $G$ has $n$ vertices and $m$ arcs, then $G^*$ has $m$ vertices and $\min(n^3,m^2)$ arcs. Computing the dominator tree can be done in nearly linear time (see e.g., https://en.wikipedia.org/wiki/Dominator_(graph_theory)#Algorithms or Dominator Tree for DAG). The Union-Find algorithm can be done in nearly linear time. Thus, the running time is essentially $O(\min(n^3,m^2))$, ignoring logarithmic factors.

I wouldn't be surprised if there is a more efficient way to compute the dominator tree of $G^*$ without constructing $G^*$ explicitly, which would lead to improvements in the running time of this algorithm.

Proofs

Proof of Lemma 1. If $P(a_1) \ne P(a_2)$, there is some path that goes through $a_1$ but not $a_2$ (or vice versa), and then by the requirements, $a_1,a_2$ cannot be given the same color.

For the converse, suppose we form equivalence classes on the arcs where $a_1,a_2$ are equivalent if $P(a_1)=P(a_2)$, give each equivalence class a unique color, and color each edge according to the color of the equivalence class it is contained in. Then this satisfies all of the constraints: for any color $c$ and any two arcs $a_1,a_2$ colored $c$, we have $P(a_1)=P(a_2)$, so any path $p \in P(a_1)$ also satisfies $p \in P(a_2)$ and thus visits $a_2$; and any path $p \notin P(a_1)$ also satisfies $p \notin P(a_2)$ and thus does not visit $a_2$.

I haven't written out the proofs of Lemmas 2-3, so I recommend you do that and check my reasoning before using this algorithm.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Is Union-Find necessary? It seems your algorithm can be combined with Pål GD's greedy algorithm: Every time you fan in, just check if the out-edge is the post-dominator of its dominator. $\endgroup$ – xskxzr Sep 27 at 10:52
  • $\begingroup$ @xskxzr, oh, neat! Thank you for sharing that improvement. $\endgroup$ – D.W. Sep 27 at 17:43
3
$\begingroup$

There is a simple randomized linear-time algorithm (one-sided error). It is based on HEKTO's idea, using the equivalent relation.

The algorithm chooses weight $w_a$ for each arc $a$. Then, the algorithm computes the weighted sum of paths $W(a) = \sum_{p \in P(a)} \prod_{a' \in p} w_{a'}$ for each each arc $a$. All $W$ values can be computed by using two dynamic programming (combining "forward" DP and "backward" DP) and in $\Theta(n + m)$ arithmetic operations. The algorithm then assign one color for each $W$ value, using a hash map.

Pseudo code:

forward = [ 1 if it is the source, 0 otherwise | vertices ]
for each arc a in topological order:
    forward[a.to] += forward[a.from] * w[a]

backward = [ 1 if it is the destination, 0 otherwise | vertices ]
for each arc a in reverse topological order:
    backward[a.from] += w[a] * backward[a.to]

for each arc a:
    W[a] = forward[a.from] * w[a] * backward[a.to]

It is easy to see $W(a) = W(b)$ if and only if $P(a) = P(b)$ if weights $w$ are treated as formal variables. According to Schwartz–Zippel lemma, if we choose weight randomly from a finite field $F$, then one particular equality fails in at most probability $m/|F|$. The overall success probability of the algorithm can be bounded by $1 - m^3 / 2|F|$ because we have at most $m \choose 2$ equations we want to distinguish, but it should be more like $\approx 1 - m^2/|F|$ for "typical input" (though I'm not very sure). We can choose a large prime of size $p \approx 2^{64}$ and do a modular arithmetic $F = GF(p)$ to implement the algorithm.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Beautiful! I would upvote multiple times if I could. $\endgroup$ – D.W. Sep 26 at 21:13
  • $\begingroup$ Interesting idea! What if instead randomization to assign sequential prime numbers to all the arcs, and then to use product instead of summation over paths? It looks like in this case pathset weights will have unique factorization, so there won't be false positives. $\endgroup$ – HEKTO Sep 30 at 1:37
  • $\begingroup$ @HEKTO I don't think that works. In general, we have to work on a finite field because otherwise we will get exponentially big numbers and thus we will have worse time complexity. $\endgroup$ – pcpthm Oct 1 at 12:21
  • $\begingroup$ I've added another answer, where I use some of your ideas - thanks! But no randomization $\endgroup$ – HEKTO Oct 3 at 1:10
2
$\begingroup$

This answer is an improvement for my (already accepted) original answer, which describes an exact, but potentially very slow algorithm. This improvement was inspired by the @pcpthm answer, however I don't employ any randomization here, so this algorithm also produces the exact coloring.

For each arc $a \in A$ let's consider a set of arcs $R(a) \subset A$, reachable from the arc $a$ in both forward and backward directions. Any arc $a \in A$ is reachable from itself, so $a \in R(a)$. We can color a pair of arcs $(a_1,a_2)$ by the same color, if and only if $R(a_1) = R(a_2)$. So, as in my original answer, we can define an equivalence relation on the set $A$:

$$(a_1 \sim a_2) \equiv (R(a_1) = R(a_2))$$

A minimum number of colors, needed to color all the arcs in the graph $G$ according to your restriction, will be equal to the number of equivalence classes for the relation above.

We can compute sets $R(a)$ for each arc $a \in A$, using the iterative process, similar to one, described in the @pcpthm answer. For each vertex $u \in V$ we define two sets of arcs - a set $F(u) \subset A$ of arcs, forward-reachable from the vertex $u$, and a set $B(u) \subset A$ of arcs, backward-reachable from the vertex $u$. For any arc $a=(u,v)$ we can represent its $R(a)$ as a union of three non-intersecting sets:

$$R(a) = B(u) \cup \{(u,v)\} \cup F(v)$$

Sets $F(u)$ and $B(u)$ for each vertex $u \in V$ can be computed using topological ordering on the set $V$. For example, the backward (according to this ordering) scan of the set $V$ will give us all the sets $F(u)$ using the formula:

$$F(u) = \bigcup_{v \in N_{out}(u)}(\{(u,v)\} \cup F(v))$$

where $N_{out}(u)$ - open "out"-neighborhood of the vertex $u$. Each such set can be represented by a binary number of the length $m=|A|$. The union operation here for large $m$ can be performed in $O(m)$ time, so the total time to compute all the $R(a)$ will be $O((n+m)m)$.

This algorithm is slower than the randomized algorithm in the @pcpthm answer, however it looks like it's the price we need to pay for the exact solution. The culprit is a necessity to work with large sets of arcs, which can't be represented by a single machine word.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Nice! Can you share the justification for why two nodes $a_1,a_2$ can be given the same color iff $R(a_1)=R(a_2)$? Is there a sketch of a proof for that fact? $\endgroup$ – D.W. Oct 3 at 5:50
  • $\begingroup$ @D.W. - if $R(u_1,v_1)=R(u_2,v_2)$ and $(u_1,v_1)$ is "earlier" than $(u_2,v_2)$, then this set must be a union of five non-intersecting sets $B(u_1) \cup \{(u_1,v_1)\} \cup (F(v_1 \cap B(u_2)) \cup \{(u_2,v_2)\} \cup F(v_2)$. I can't prove that, but I feel that this decomposition is only way we can guarantee the equality of these two sets. Then we can see that all paths, passing through $(u_1,v_1)$, must also pass through $(u_2,v_2)$. $\endgroup$ – HEKTO Oct 4 at 0:53

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.