# #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:
begin{align*} 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 end{align*}
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!!!

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