# approaching dynamic programing for problem

This problem is easily solved if you:

• transform the input graph $$G=(V,E)$$ by either creating $$n-1$$ “levels”, where each level is a copy of $$G$$ and edges go from one level to the next; or
• consider the line graph $$G’$$ of $$G$$ instead (so that edges in $$G$$ become vertices in $$G’$$, and two vertices in $$G’$$ are adjacent if the corresponding edges in $$G$$ share an endpoint); or
• For each color $$c in {red, blue}$$, identify the maximal components $$C$$ of $$G$$ such that connectivity within $$C$$ is preserved using only edges of color $$c$$.

If you insist in using a dynamic programming algorithm, then the problem can be solved in $$O(m)$$ time using a Dijkstra-like algorithm.

Given a color $$c in {red, blue}$$, define a $$c$$-ending path as a simple path $$P$$ such that either 1) $$P$$ is empty, or 2) $$P$$ ends with an edge of color $$c$$.

Given a path $$P$$, let $$ell(P)$$ be the number of color changes encountered when traversing $$P$$.
We will say a path $$P$$ from $$s$$ to $$v$$ is a shortest $$c$$-ending path if there exist no other $$c$$-ending path $$P’$$ such that $$ell(P’) < ell(P)$$.

We will call $$eta(v,c)$$ the value of $$ell(P)$$, where $$P$$ is a shortest $$c$$-ending path from $$s$$ to $$v$$.

According to the above definitions $$eta(s, red) = eta(s, blue) = 0$$.
Moreover, the following suboptimality property holds:

Claim: Let $$P$$ be any shortest $$c$$-ending path from $$s$$ to $$v$$, let $$u in P$$.
The subpath $$P(s:u)$$ of $$P$$ going from $$s$$ to $$u$$ is a shortest $$c’$$-ending path where $$c’$$ is the color of the incoming edge in $$u$$ (if $$u=s$$ then $$c’$$ is any color).

Proof:
Assume that $$u neq v$$, otherwise the claim is trivial.
Let $$c”$$ be the color of the edge leaving $$u$$ in $$P$$.

Suppose towards a contradiction that $$P(s:u)$$ is not a shortest $$c’$$-ending path.
Let $$P’$$ be a shortest $$c’$$-ending path from $$s$$ to $$u$$, and notice that $$Q = P’ circ P(u:v)$$ is a (not necessarily simple) path from $$s$$ to $$v$$.
$$Q$$ ends with an edge of color $$c$$ and we have:
$$ell(P) = ell(P(s:u)) + 1_{c’ neq c”} + ell(P(u:v)) > ell(P’) + 1_{c’ neq c”} + ell(P(u:v)) = ell(Q),$$
contradicting the fact that $$P$$ is a shortest $$c$$-ending path. $$square$$

For each node $$v$$ we will maintain two upper bound $$tilde{eta}(v, red)$$ and $$tilde{eta}(v, blue)$$ on $$eta(v, red)$$ and $$eta(v, blue)$$, respectively. Initially $$tilde{eta}(s, red)=tilde{eta}(s, blue)=eta(s, red) = eta(s, blue) = 0$$ while, for $$v neq s$$, $$tilde{eta}(s, red)=tilde{eta}(s, blue) = +infty$$.

Finally, we will maintain a priority queue $$Q$$ in which keys are pairs $$(v,c)$$ where $$v$$ is an unmarked vertex and $$c$$ is a color, and the corresponding priority will be $$tilde{eta}(v, c)$$. Initially all pairs $$(v,c)$$ are in the queue.

The algorithm proceeds as follows: while $$Q$$ is not empty, extract $$(u,c)$$ from $$Q$$; for each edge $$e=(u,v) in E$$ let $$c’$$ be the color of $$e$$ and set $$tilde{eta}(v, c) = min{tilde{eta}(v, c), tilde{eta}(u, c) + 1_{c neq c’} }$$ (thus possibly updating the priority of $$(v,c)$$, if such a pair is in $$Q$$).

It is clear by construction that all values $$tilde{eta}(v, c)$$ are upper bounds to $$eta(v,c)$$ as claimed. We now prove that, when the pair $$(v,c)$$ is extracted from $$Q$$, $$tilde{eta}(v, c)$$ is also a lower bound to $$eta(v,c)$$, thus proving that $$tilde{eta}(v, c) = eta(v,c)$$.

Claim: When $$i$$-th pair $$(v_i,c_i)$$ is extracted from $$Q$$, $$tilde{eta}(v, c) le eta(v,c)$$.

Proof:
Let $$i$$ be the smallest value such that, when $$(v_i, c_i)$$ is extracted from $$Q$$ we have $$tilde{eta}(v_i, c_i) > eta(v_i,c_i)$$.

Since the values $$tilde{eta}(v_i, c_i)$$ never decrease during the execution of the algorithm and cannot become negative we know that $$v_i neq s$$.
Let $$P$$ be a shortest $$c_i$$-ending path from $$s$$ to $$v_i$$ and consider the last vertex $$x$$ such that the incoming edge in $$x$$ in $$P$$ has color $$c_x$$ (if $$x=s$$ let $$c_x$$ be any color) and $$x=v_j$$ and $$c_x=c_j$$ for some $$j (notice such a vertex always exists since the above conditions are satisfied for $$x=s$$).
Let $$y$$ be the vertex following $$x$$ in $$P$$ and $$c_y$$ be the color of the incoming edge.

Since $$(v_i, c_i)$$ was extracted instead of $$(y, c_y)$$ we must have:
$$tildeeta(v_i, c_i) le tildeeta(y, c_y)$$

Moreover, since $$(x, c_x)$$ was already extracted from $$q$$ we have:
$$tildeeta(y, c_y) le tildeeta(x, c_x) + 1_{c_x neq x_y} = eta(x, c_x) + 1_{c_x neq x_y}$$

And, by suboptimality:
$$eta(x, c_x) + 1_{c_x neq x_y} = eta(y, c_y) le eta(v_i,c_i),$$
which is a contradiction $$square$$.

The sought quantity is then $$min{tildeeta(t,red), tildeeta(t,blue) }$$.

Finally, notice that the the priority can only decrease in $$Q$$, that the priority of the extracted pairs is monotonically increasing, and that the only possible values of the priorities are $${0, 1, dots, n} cup { +infty }$$. Therefore it is possible to implement a priority $$Q$$ that requires $$O(n+m) = O(m)$$ time to perform all the required $$O(n)$$ insertions and $$O(m)$$ priority updates.