3
$\begingroup$

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'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$.
    Consequently $w(e_{ij})$ can be different from $w(e_{ji})$

  • 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.

$\endgroup$
3
$\begingroup$

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$.

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.