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_1\to y_1) = w(x_2\to y_2) &= 1 \\ w(y_2\to x_1) = w(y_1\to x_2) &= -2 \\ w(x_3\to y_3) = w(x_4\to y_4) &= 5 \\ w(y_4\to x_3) = w(y_3\to x_4) &= -3 \end{align*} and all other weights are $+\infty$.
There is a negative cycle $x_1\to y_1\to x_2\to 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.