Maximum weighted bipartite matching _with_ directe

2019-05-23 14:59发布

问题:

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:

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.