Maximum weighted bipartite matching _with_ directed edges

2
votes

I know various algorithms to compute the maximum weighted matching of weighted, undirected bipartite graphs (i.e. the assignment problem):

For instance ... The Hungarian Algorithm, Bellman-Ford or even the Blossom algorithm (which works for general, i.e. not bipartite, graphs).

However, how can I compute the maximum weighted matching if the edges of the bipartite graph are weighted and directed?

I would appreciate pointers to algorithms with polinomial complexity or prior transformations to make the graph undirected so that I could apply any of the aforementioned algorithms.

Edit: note that the matching should maximize the weight of the edges, that's why having directed edges makes a difference (A->B can have a totally different weight than B->A).

Admittedly, if I was maximizing cardinality, the directed edges wouldn't make a difference and I could apply any of the well-known algorithms to maximize cardinality: Hopcroft–Karp, Maximum Network Flow ....

Edit 2: Since matching is a term normally applied to undirected graphs, let me clarify what I exactly mean by matching in this question: a set of directed edges that do not share start or end vertices. More formally, if U->V and U'->V' are part of the matching, then V /= U' and V' /= U.

1
algorithmgraphcomplexity-theorymatching
How does directedness come into this? Maybe it's just me, but to me it's unclear how a directed matching differs from an undirected one. Is a set of edges only a matching if all its edges go from part A to part B of the graph? But then, it would be trivial to reduce this to the undirected case. – us2012
Huh? A bipartite graph may not be directional, but any max-flow algorithm will make the implicit transformation that all edges are directed from set A to set B. Even if you had a directed bipartite graph, how is A->B different from B->A in the context of a matching problem? – dfb
Directedness makes a diference because different edges (with different directions) may have different weights. Let G = (U u V, E) be a directed bipartite graph, let u be a node from U and v a node from V. The weight assigned to edge u -> v may be different to the weight assigned to the edge v -> u It wouldn't make a difference if the matching maximized cardinality but I am referring to a matching maximizing weight. – fons
Seems if there are separate weights x=A->B y=B->A then you can discard B->A and set the x=max(x,y) and run the regular algorithm – dfb
What do you mean by "matching"? ('Cause it obviously isn't just a set of edges, no two of which share an end.) – tmyklebu

1 Answers

2
votes

dfb's comment is correct, for any two vertices A, B you can discard the cheaper of the two edges AB and BA.

The proof is a one-liner:

Theorem: A maximum matching M never contains the cheaper edge of AB and BA for any two vertices A,B.

Proof: Let M be a maximum matching. Suppose AB is in M and is cheaper than BA. Define M' = M - {AB} + {BA}. M' is clearly still a matching, but it's more expensive. That contraditcs the assumption that M was a maximum matching.