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.

• Optidad: If your graph is not very dense, it might be interesting to first identify the SCC (for instance using the linear time Tarjan's algorithm). Then you look for negative loop separately in each SCC. This is of course no help for the very general problem.

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.