# approaching dynamic programing for problem

I want to find a solution to a problem that asked before. in the following question: https://stackoverflow.com/questions/43435799/path-with-the-minimum-number-of-alterations-in-graph-with-colored-edgest

I have a directed graph with colored edges (red & blue) that may contain cycles. The question is to write an algorithm given two vertices (s,t) that finds the path with the minimal number of color changes between s and t (if such path exists). $suggesting a reduction to solve the problem. I want to find an optimal structure for the problem by: $$opt(v) = \min_{u \in In(v)}(opt(u) + f(u,v))$$ $$f(u,v)$$ define: $$f(u,v) = \begin{cases} 1, & \text{the color of (u,v) same as the color that appears more}, \\ -1, & \text{the color of (u,v) the color different from the color that appears more}.\\ 1, & \text{else} \end{cases}$$ the problem with that formula is that the optimum of the neighbors, not gratitude the optimum solution for $$v$$ because considering v that have 1 neighbor with a blue edge that has a path with the same blue and red edges and another path with 1 more red edge than my structure return 1 however there is a path with 0 alterations. then I thinking to save for all the vertices 3 paths, optimum path most optimum path with more blue and path with more red but its seem to complicated to build a formula with that filed. • Hint: I can think of 2 ways to solve this. (1)$opt(v)\$ remembers the optimal solution per vertex, but is this enough information to build solutions to larger subproblems? Maybe you need to instead remember the optimal solution per _____. (2) Transform the graph somehow. Nov 17, 2020 at 15:01
• @j_random_hacker the assignment publisher note that we not allowed to transform the graph. Nov 17, 2020 at 15:08

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. Let's start with some definitions:

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: $$\tilde\eta(v_i, c_i) \le \tilde\eta(y, c_y)$$

Moreover, since $$(x, c_x)$$ was already extracted from $$q$$ we have: $$\tilde\eta(y, c_y) \le \tilde\eta(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\{\tilde\eta(t,red), \tilde\eta(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.