#StackBounty: #algorithms #graphs #shortest-path Finding a negative cycle in a bipartite graph

Bounty: 50

The Bellman-Ford algorithm can be used to find a negative cycle in a general graph, in time $O(|V||E|)$. Is there a faster algorithm for finding a negative cycle in a bipartite directed graph, where the edges in one direction (from X to Y) are all positive and the edges in the other direction (from Y to X) are all negative?

One idea that I considered is to solve two instances of the minimum-weight assignment problem: one with only the edges from X to Y, and one with only the edges from Y to X. Combining the two assignments gives a directed cycle in the original graph. However there are two problems with this idea:

  • The computational problem of finding a minimum-weight assignment is not necessarily smaller than Bellman-Ford, for example the Hungarian algorithm requires time $O(|V|^3)$.
  • The directed cycle found in this way is not necessarily minimum-weight in the original graph; it is possible that the original graph has a negative cycle while this algorithm will yield only a positive cycle. For example, consider a graph with four vertices in each side, with the following weights:
    w(x_1to y_1) = w(x_2to y_2) &= 1
    w(y_2to x_1) = w(y_1to x_2) &= -2
    w(x_3to y_3) = w(x_4to y_4) &= 5
    w(y_4to x_3) = w(y_3to x_4) &= -3

    and all other weights are $+infty$.

There is a negative cycle $x_1to y_1to x_2to y_2$ (total weight -2). However, the minimum-weight assignment from X to Y has weight 12 and the minimum-weight assignment from Y to X has weight -10 so the total is positive.

Get this bounty!!!

Leave a Reply

This site uses Akismet to reduce spam. Learn how your comment data is processed.