Finding a negative cycle in a bipartite graph

Question

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.

Answer 1

Given a directed graph, turn each edge $(u,v)$ into two edges $(u, x)$ and $(x,v)$ with the same weight where $x$ is a newly added vertex. Now the graph becomes a bipartite graph, and there is a negative cycle in the original graph if and only if there is a negative cycle in the new bipartite graph.

Suppose the two parts of the bipartite graph are $X$ and $Y$. We increase the weights of all edges from $X$ to $Y$ by $r$ and decrease the weights of all edges from $Y$ to $X$ by $r$, where $r$ is a large enough positive integer. Now we get a new bipartite graph where all edges from $X$ to $Y$ have positive weights and all edges from $Y$ to $X$ have negative weights. In addition, there is a negative cycle in the original bipartite graph if and only if there is a negative cycle in the new bipartite graph.

So if there is an $O(f(|V|,|E|))$ algorithm to solve your problem, we can solve the problem on general directed graphs in $O(|E|+f(|V|,|E|))=O(f(|V|,|E|))$ (since $f(|V|,|E|)\in \Omega(|E|)$) time by applying the algorithm on the bipartite graph obtained from the conversion above. This means your problem is asymptotically no easier than the problem on general directed graphs.