0
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ 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. $\endgroup$ Nov 17, 2020 at 15:01
  • $\begingroup$ @j_random_hacker the assignment publisher note that we not allowed to transform the graph. $\endgroup$
    – OriFrid
    Nov 17, 2020 at 15:08

1 Answer 1

0
$\begingroup$

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<i$ (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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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