# Bellman-Ford and zero-distance cycle

Problem statement: Given a graph G(V,E) which is not acyclic and may have negative edge weights (and thus may possibly have negative-length cycles), how does one detect if the graph has a zero-length cycle, and no negative-length cycles?

Background information: The question came up when I tried to implement in code the solution to what is called the "tramp steamer" problem: Given a graph G(V,E) in which each node is associated with a cost $c_i$ and each edge is associated with a time (number of days) $t_i$, find the cycle with the smallest ratio of cost to time $\frac{\sum_i(c_i)}{\sum_i(t_i)}$ (i.e. minimal cost/day cycle).

One solution is to do a binary search with the range of possible rations, trying to identify the minimum cost-to-time ratio $\mu$. In each iteration of the binary search in the range $[left...right]$, you "guess" a value of $\mu = \frac{left+right}{2}$ and then run Bellman-Ford:

• if a negative cycle exists then the value of $\mu$ is too high; the range is reset to $[left...\mu]$
• if all cycles are positive then the value of $\mu$ is too low; the range is reset to $[\mu...right]$
• if there is a zero-length cycle (with all other cycles being positive), then we have found the best value for $\mu$ and we can stop, returning the zero-length cycle as the answer

How exactly is the third case detected? Assume the graph A->B->C->D->{A,B} with two cycles (fro D back to A or B) where the cycle B->C->D->B is the optimal one and yields zero length for some selection of $\mu$ for which the other cycle is positive. Suppose we happen to try this particular value of $\mu$ (let's assume it's during the very first iteration because we got lucky). If I am using vertex A as the fixed point from which I run Bellman-Ford on each iteration, it will complete successfully without detecting a negative cycle. But how would the zero-length cycle be identified?

Currently I only handle the first 2 cases and my implementation keeps iterating until the $[left...right]$ range becomes becomes too small, so that floating point precision can't handle a smaller range. At that point I detect that $\frac{left+right}{2}$ is equal to one of the range limits (either left or right) and stop the binary search. How would I go about detecting that a particular value of $\mu$ has produced a zero-length cycle?

Here's how you can detect whether a weighted graph $G$ contains a zero-length cycle, assuming it does not contain any negative cycle.

1. Run Bellman-Ford on it to compute the distance $d(v)$ from the source to $v$, for each vertex $v$.

2. Color each edge $(v,w)$ red if $d(v) + \text{wt}(v,w) = d(w)$.

3. Form a new unweighted, directed graph $G'$ containing just the red edges from $G$. Check whether $G'$ has any cycles, using a standard algorithm (e.g., depth-first search). This can be done in linear time.

I'll leave it to you as an exercise to prove that the original graph $G$ contains a zero-length cycle if and only if the new graph $G'$ has a cycle.

• what is the complexity of this algorithm?
– Mr.
Apr 25 '18 at 4:25
• @Turbo, you should be able to figure that out on your own. Try figuring out the complexity of each of hte 3 steps, separately.
– D.W.
Apr 25 '18 at 15:47
• @D.W. How can you run Bellman-Ford, if you don't have a source vertex?
– Dani
Jan 26 at 9:38

Note that this answer only contains the proof that was left as an exercise by D.W.. First, give it a try by yourself. And, in case you get stuck then refer to it.

Statement: The original graph $$G$$ contains a zero-length cycle if and only if the new graph $$G′$$ has a cycle.

Proof: Let $$d_{s}(v)$$ denote the shortest path length from $$s$$ to $$v$$ for any $$v \in V$$. First, we will prove the "only if" direction.

$$(\to)$$ Suppose $$G$$ contains a zero weight cycle $$C = (u_{1},\dotsc,u_{k} )$$. For the sake of contradiction assume that $$G'$$ does not contain this cycle. It means there are some two vertices in $$C$$, say $$u_{1}$$ and $$u_{2}$$ for which $$d_{s}(u_{2}) \neq d_{s}(u_{1}) + w(u_{1},u_{2})$$. It means, $$d_{s}(u_{2}) < d_{s}(u_{1}) + w(u_{1},u_{2})$$. Let us call this equation $$(1)$$.

Now, consider the path $$p$$ from $$s$$ to $$u_{1}$$ as: $$s$$ -> $$u_{2}\dotsc$$->$$u_{k}$$->$$u_{1}$$. The length of this path is: $$(d_{s}(u_{2}) + length(u_{2} \textrm{ to } u_{1}))$$. Since $$length(u_{2} \textrm{ to } u_{1})+ w(u_{1},u_{2}) = 0$$. The length of $$p$$ is: $$(d_{s}(u_{2}) - w(u_{1},u_{2}))$$. From equation $$(1)$$, this value is at $$< d_{s}(u_{1})$$. It contradicts the fact that the shortest path length from $$s$$ to $$u_{1}$$ is $$d_{s}(u_{1})$$. This completes the proof of "only if" direction. Now, we will prove the other direction.

$$(\gets)$$ Suppose $$G'$$ has a cycle $$C = (u_{1},\dotsc,u_{k} )$$. We will show that the weight of this cycle is $$0$$.

Let $$u_{1}$$ and $$u_{2}$$ be the two vertices in $$C$$. We have that:

\begin{align} d_{s}(u_{1}) &= d_{s}(u_{k}) + w(u_{k},u_{1}) \\ &= d_{s}(u_{k-1}) + w(u_{k-1},u_{k}) + w(u_{k},u_{1})\\ &\quad ... continuing \\ &= d_{s}(u_{2}) + w(u_{2},u_{3}) + \dotsc + w(u_{k},u_{1}) \\ &= d_{s}(u_{1}) + w(u_{1},u_{2}) + w(u_{2},u_{3}) + \dotsc + w(u_{k},u_{1}) \\ &= d_{s}(u_{1}) + length(C)\\ \end{align}

It implies that the length of the cycle is $$0$$. This completes the proof of "if" direction.

I don't think there is a known algorithm to find whether there is a zero-distance cycle in a graph in a polynomial time, as it is an NP-complete problem.

As you might know, if a known NP-Complete problem $X$ can be reduced in polynomial time to another problem $Y$ ($X \leqslant_p Y$) then $Y$ is an NP-complete problem too. Such is the case with Zero-distance cycle problem (which I will call $Z$) and the Subset Sum Problem (which I will call $S$).

$S$ is a known NP-Complete problem. A proof of its NP-Completeness can be found in chapter 8, section 8.8 of Algorithm Design, by Jon Kleinberg and Éva Tardos. It reduces SAT to 3D-Matching to Subset-Sum. It has another version of $S$, but it can be proven equivalent by polynomial reduction with the one used in this answer.

Now, here's a proof of how $S \leqslant_p Z$:

Suppose you have an $S$ problem. Its input is a set $W = \{w_1, \ldots, w_n\} \subseteq \mathbb{Z}$. The input is accepted by $S$ if there is a subset $A \subseteq W$ so that

$$\sum_{a \in A} a = 0.$$

So let's model this $S$ problem as a $Z$ problem. To do so, we build a Graph $G = (V,E)$ with $2n$ vertices as follows:

• For each element $w_i$ we create two vertices, $u_i$ and $v_i$.
• For every $v_i$ we add the edge $(v_i,u_i)$ to $E$ with weight $w_i$.
• For every $u_i$ and $v_j$ we add the edge $(u_i, v_j)$ to $E$ with weight $0$.

For a three element $S$ problem we would get a graph such as this: Now, we send that graph to an hypothetic $Z$ solver. Some important notes:

• If there is a cycle, it goes through at least one complete element ($u_i$ and $v_i$).
• If a cycle goes through such an element, the total distance increments by $w_i$.
• If a cycle goes through multiple elements, the total distance will be the sum of all of them.

As a conclusion, if a zero-distance cycle is found by the $Z$ solver, that would mean that there is a subset of $W$ with zero sum. This confirms that $S \leqslant_p Z$, and because of that $Z$ is NP-Complete.

• Your reduction seems wrong. Take for instance the set $\{-2,1\}$. In the graph you obtain, there is a 0-cycle which needs to take twice the value $1$, however there is no solution to the $S$-problem. Actually, testing the existence of a $0$-cycle in a directed graph (even in multiple dimensions) is known to be solvable in PTime. See (dl.acm.org/citation.cfm?id=62251).
– manu
Mar 23 '18 at 14:49