0
$\begingroup$

Please Note: I forgot a small detail which caused the algorithm to be incorrect, please read the new version and thanks for pointing that.


I am stuck on this question for a week and hope to get some help:

Algorithm:

Given 2 sided Graph ie bipartite graph G(L,R,E), a weight function and a root vertex s:

  1. Define E1 as the group of edges connecting vertex from L to R
    (the rest are in E2 Group).
  2. For each vertex v, let
    d(v) = ∞ except d(s) = 0
  3. Do (|L|+|R|)/2 (round floor) iterations of the following:

Check Every edge in the graph, while finishing all edges > in E1 and only then moving on to E2: if d(v)>d(u)+w(u,v) then let d(v)=d(u)+w(u,v)

Prove that if there is no circular path with total negative weight in G, then the given algorithm returns for each vertex v the minimal weight of a path from s to v.


My try:

  • For every vertex v we can conclude that there is a shortest path from s which is simple (no vertex appears twice, else we are getting a contradiction to the fact that there is no negative circular paths)

  • The difference between number of edges from E1 and E2 is no more than 1

  • For every simple and short path P there is no more than (|L|+|R|)/2 (round floor) edges from E1 (and the same for E2).

Claim: For every vertex v if there is a shortest path $P$ from s to v , which contains $k$ edges from $E1$ then at the end of k-th iteration d(v)=|P| ie the algorithm's calculation is correct.

Proof: By induction on k.


But as I progressed it seemed that the claim doesn't cover all cases (Thus it's wrong). For example, it worked when v is in R group but failed To help prove the case when v is in L group.

Thanks in advance for any help

New contributor
coolmo is a new contributor to this site. Take care in asking for clarification, commenting, and answering. Check out our Code of Conduct.
$\endgroup$
7
  • $\begingroup$ Any help please on what should the claim be? (as mine is wrong or isn't helpful to prove correctness) $\endgroup$ – coolmo Jun 5 at 21:35
  • $\begingroup$ Prove by induction on the number of iterations that at the end of iteration $i$ all values $d(u)$ where $u$ is at distance at most $2i$ from $s$ are exactly the distance from $s$ to $u$ in $G$. $\endgroup$ – Steven Jun 5 at 21:43
  • $\begingroup$ Another, less precise, way to show the result is noticing that each iteration of your algorithm corresponds to two iterations of the Bellman-Ford algorithm. Since the correctness of the Bellman-Ford algorithm does not depend on the order in which edges are examined (which can be different between iterations) we are free to choose our own edge order. $\endgroup$ – Steven Jun 5 at 23:10
  • $\begingroup$ In details, an iteration of your algorithm yields the same distances obtained by performing 1) an iteration of Bellman-Ford in which edges in $E_2$ are examined before those in $E_1$ (here no distance is updated while examining $E_2$), and 2) and iteration of Bellman-Ford in which edges in $E_1$ are examined before those in $E_2$ (no distance is actually updated while examining $E_1$). $\endgroup$ – Steven Jun 5 at 23:10
  • $\begingroup$ @Steven I tried induction and that's where I stuck, I said let P be the shortest path from u to v of lengh n, ie P: u->...->w->v. I said let's look at u->...->w which is of length n-1 so according to the assumption we know that d(w)=s(u,w). But how this can help me say that d(v)=s(u,v)? I proved that at every moment s(s,v)<=d(v) if that helps. Thanks $\endgroup$ – coolmo Jun 6 at 0:34
1
$\begingroup$

Let $D(t,i)$ denote the length of the shortest among the path from $s$ to $t$ in $G$ that use at most $i$ edges.

We will focus on the generic $i$-th iteration of the algorithm and show that:

  • (i) after all the edges in $E_1$ have been considered, we must have $d(t) \le D(t, 2i)$ for each vertex $t \in R$.
  • (ii) after all the edges in $E_2$ have been considered, we must have $d(t) \le D(t, 2i)$ for each vertex $t \in L$.

As an edge case we consider the $0$-th iteration to be completed immediately before the start of the for loop.

The proof is by induction on $i$. The base case $i=0$ is trivially true since the only vertex at hop-distance $0$ from $s$ is $s \in L$ itself and the algorithm explicitly sets $d(s) = 0 = D(s, 0)$.

Consider now $i > 0$. If $t=s$ we know, by induction hypothesis, that after iteration $0$ we have $d(s) \le D(s,0) \le D(s, 2i)$. Therefore, we restrict ourselves to the case in which $t \neq $ s and $D(t, 2i)$ is finite. Let $(v,t)$ be the last edge in any shortest path from $s$ to $t$ in $G$ that uses at most $2i$ edges.

If $t \in R$ then $v \in L$ and all paths to $v$ have even hop-length. Therefore, when $(v,t) \in E_1$ is considered, we have $d(v) \le D(v, 2(i-1))$ by induction hypothesis and hence: $$ D(t, 2i) = D(v, 2i-1) + w(v,t) = D(v, 2(i-1)) + w(v,t) \ge d(v)+w(t). $$ This ensures that, after examining $(v,t)$ in iteration $i$ we must have $d(t) \le d(v)+w(t) \le D(t, 2i)$ and proves (i).

If $t \in L$ then $v \in R$ and all paths to $v$ have odd hop-length. When $(v,t) \in E_2$ is considered we have $d(v) \le D(v, 2i)$ (this follows from (i), which we just proved). Therefore: $$ D(t, 2i) = D(v, 2i-1) + w(v,t) = D(v, 2i) + w(v,t) \ge d(v) + w(v,t). $$ Therefore, after $(v,t)$ is examined, we must have $d(t) \le D(t, 2i)$. This proves (ii) and concludes the proof by induction.

At this point we just need to notice that, the above claim, implies that at the end of the algorithm $d(t)$ is at most $D(t, 2 \lfloor (|L|+|R|)/2\rfloor) \le D(t, |L|+|R|-1)$, where $D(t, |L|+|R|-1)$ is exactly the distance from $s$ to $t$ in $G$. Moreover, all (finite) distances $d(t)$ computed by the algorithm correspond to the length of an actual path to $t$ in $G$, showing that $d(t)$ is also not smaller than the distance from $s$ to $t$ in $G$.


This part of the answer refers to a previous version of the question in which the Algotithm did not prescribe any particular order in which to consider the edges

If by 2-sided graph you mean bipartite graph, then the algorithm is wrong.

As a counterexample consider the graph $G=(L \cup R, E)$ where $L = \{s, \ell\}$, $R =\{r\}$ $E=\{(s,r), (r, \ell)\}$, and all edge weights are $1$. The algorithm will perform $\left\lfloor \frac{|L|+|R|}{2} \right\rfloor = 1$ iteration. Since there is no prescribed order in which the edges are considered, we can look at the case in which $(r, \ell)$ is considered before $(s, \ell)$.

When $(r, \ell)$ is examined, the condition of the if statement is not satisfied, so $d(\ell)$ is not updated. Moreover, when $(s, r)$ is considered only $d(r)$ can possibly be updated, so $d(\ell)$ is unchanged.

This shows that at the end of the algorithm $d(\ell) = + \infty$ but the distance between $s$ and $\ell$ in $G$ is $2$.

$\endgroup$
1
  • $\begingroup$ So sorry my fault, the actual question said to run E1 before E2 and I ignored that by mistake. Please keep this as it's helpful and hope if you can help me fix my proof and continue it. $\endgroup$ – coolmo Jun 5 at 20:00

Your Answer

coolmo is a new contributor. Be nice, and check out our Code of Conduct.

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.