3
$\begingroup$

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?

$\endgroup$
3
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ what is the complexity of this algorithm? $\endgroup$ – Brout Apr 25 '18 at 4:25
  • $\begingroup$ @Turbo, you should be able to figure that out on your own. Try figuring out the complexity of each of hte 3 steps, separately. $\endgroup$ – D.W. Apr 25 '18 at 15:47
-1
$\begingroup$

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:

Reduction example for three elements.

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.

$\endgroup$
  • 1
    $\begingroup$ 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). $\endgroup$ – manu Mar 23 '18 at 14:49

Your Answer

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.