Bellman-Ford and zero-distance cycle

Question

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?

Answer 1

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.

Answer 2

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.

Answer 3

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.