If $G\left(A\cup B,\ E=\lbrace\lbrace a, b\rbrace\,|\, a\in A,\, b\in B\rbrace\right)$ is a weighted bipartite graph and $M\_0$ an initial perfect matching, then the optimality of $M\_0$ can be verified by the absence of negative cycles in the associated residual network $N\left(V=A\cup B,\,F=\lbrace(a\_i,b\_j)\,|\,e\_{ij}\notin M\_0\rbrace\cup\lbrace(b\_j,a\_i)\,|\,e\_{ij}\in M\_0\rbrace\right)$ and weights $\omega(a\_i,b\_j)=w(e\_{ij}),\,\omega(b\_j,a\_i)=-w(e\_{ij})$.


If however a negative cycles exists in $N$ then $M\_1\ :=\ (M\_0\setminus\nu)\cup \pi$, where $\nu$ and $\pi$ denote the edges of $G$ that correspond to negative, resp. positive arcs of negative cycles in $N$, has lower weight.


The apparently unconditionally recommended method for finding a the arcs of a negative cycle in $N$ is the Bellman-Ford shortest path algorithm with $O(mn)$ runtime complexity.


However it seems to me that something taylored for the special properties of the residual network $N$ could bring about a performance boost.  

The underlying idea is simple enough:  

Construct from the edges in $M\_0$ an alternative network $\mathcal{N}$, that contains arc set $\lbrace (b\_j, a\_i)\,|\,e\_{ij}\in M\_0\rbrace\cup\lbrace(a\_i,b\_{j\_0})\,|\,e\_{ij}\notin M\_0\,\land\,\omega(a\_i,b\_{j\_0})\le\omega(a\_i,b\_j)\rbrace$ where the weights of arcs are as defined for $N$. Put differently, connect the end of negative arcs with the nearest start of a different negative arc.  

As the outdegree of every arc in $\mathcal{N}$ is exactly $1$, the underlying undirected graph has the topology of a $1$-forest, a graph, in which *every* connected component has *exactly* one cycle.
Repeatedly deleting from $\mathcal{N}$ all arcs with indegree 0 (the sources) leaves a collection of directed cycles in which the negatives ones can be trivially identified as the (strongly) connected components with negative arc-weight sum.


The complexity of the suggested alternative method can be easily determined as $O(m-n/2)$ for finding the shortest positive outgoing arc of a negative one plus $O(n)$ for repeatedly removing the source nodes in $\mathcal{N}$ when executed sequentially.



> 
> **Question:**
> 
> 
> when will the proposed alternative way of detecting negative cycles in the residual network of minimum weight perfect bipartite matching fail, resp. will it always detect one if it exists?
> 
> 
> Could it ever report false positives, i.e. yield a negative cycle if there actually isn't one? If not, the proposed method could be used to do the "bulk work" before resorting to Bellman-Ford.
> 
> 
> 


  

**Addendum:**


In view of [John Machacek](https://mathoverflow.net/users/51668/john-machacek)'s answer I see the need for clarification and making things explicit.


* the task is to determine the perfect matching of minimum weight in a *symmetric* bipartite graph, however as $e\_{ij}:=\lbrace a\_i\in A,\,b\_j\in B\rbrace$ is a shorthand notation for $e\_{a\_i b\_j}=e\_{b\_j a\_i}$, the order of indices is significant and $e\_{ii}$ doesn't denote a self loop in $G$.
* the end node $a\_i$ and start node $b\_{j\_0}$ of negative arcs that are connected by the positive arc $\lbrace a\_i, b\_{j\_0}\rbrace$ must not belong to the same negative arc, i.e. $\mathcal{N}$ must not contain pairs of antiparallel arcs.



Is it possible to improve the weight of perfect bipartite matchings faster than with Bellman-Ford?
If I understand notation correctly $e\_{ij}$ is the edge $\{a\_i, b\_j\}$ in $G$. I'll let $w\_{ij}$ be the weight $e\_{ij}$. I'll give an example showing the alternative method can fail to detect a negative cycle in $N$. Consider


$$w\_{11} = \epsilon$$
$$w\_{12} = B$$
$$w\_{13} = B$$
$$w\_{21} = B$$
$$w\_{22} = A$$
$$w\_{23}= B - \epsilon$$
$$w\_{31} = B + 3\epsilon$$
$$w\_{32} = B + 2\epsilon$$
$$w\_{33} = \epsilon$$
Where $\epsilon > 0$ is small while $A$ and $B$ are large with $B < A < 2B - \epsilon$. Let $M\_0 = \{e\_{12}, e\_{21}, e\_{33}\}$. Then $N$ contains the negative cycle
$$(a\_1, b\_1), (b\_1, a\_2), (a\_2, b\_2), (b\_2,a\_1)$$
which has weight $\epsilon - B + A -B = A + \epsilon - 2B < 0$. Indeed, $M\_0$ is not minimal weight. The minimal weight matching is $M^\* = \{e\_{11}, e\_{22}, e\_{33}\}$.


In this example $\mathcal{N}$ consists of arcs
$$\{(b\_2, a\_1), (b\_1, a\_2), (b\_3, a\_3), (a\_1, b\_1), (a\_2, b\_3), (a\_3, b\_2)\}$$
or
$$\{(b\_2, a\_1), (b\_1, a\_2), (b\_3, a\_3), (a\_1, b\_1), (a\_2, b\_3), (a\_3, b\_3)\}$$
(it depends on my understanding of the definition of $\mathcal{N}$ and if $e\_{i,j\_0}$ is allowed to be in $M\_0$ or not).


Either way we fail to find a negative cycle. In the latter case the only cycle is $(a\_3, b\_3), (b\_3, a\_3)$ which has weight $0$. In the first case we have a cycle will all the arcs
$$(a\_1,b\_1), (b\_1,a\_2), (a\_2, b\_3), (b\_3, a\_3), (a\_3,b\_2), (b\_2, a\_1)$$
which has weight $\epsilon - B + (B - \epsilon) - \epsilon + (B + 2\epsilon) - B = \epsilon > 0$.


