Directed maximum weighted bipartite matching allow

问题:

Let G (U u V, E) be a weighted directed bipartite graph (i.e. U and V are the two sets of nodes of the bipartite graph and E contains directed weighted edges from U to V or from V to U). Here is an example:

In this case:

U = {A,B,C} 
V = {D,E,F} 
E = {(A->E,7), (B->D,1), (C->E,3), (F->A,9)} 

Definition: DirectionalMatching (I made up this term just to make things clearer): set of directed edges that may share the start or end vertices. That is, if U->V and U'->V' both belong to a DirectionalMatching then V /= U' and V' /= U but it may be that U = U' or V = V'.

My question: How to efficiently find a DirectionalMatching, as defined above, for a bipartite directional weighted graph which maximizes the sum of the weights of its edges?

By efficiently, I mean polynomial complexity or faster, I already know how to implement a naive brute force approach.

In the example above the maximum weighted DirectionalMatching is: {F->A,C->E,B->D}, with a value of 13.

Formally demonstrating the equivalence of this problem to any other well known problem in graph theory would also be valuable.

Thanks!

Note 1: This question is based on Maximum weighted bipartite matching _with_ directed edges but with the extra relaxation that it is allowed for edges in the matching to share the origin or destination. Since that relaxation makes a big difference, I created an independent question.

Note 2: This is a maximum weight matching. Cardinality (how many edges are present) and the number of vertices covered by the matching is irrelevant for a correct result. Only the maximum weight matters.

Note 2: During my research to solve the problem I found this paper, I think it would be helpful to others trying to find a solution: Alternating cycles and paths in edge-coloured multigraphs: a survey

Note 3: In case it helps, you can also think of the graph as its equivalent 2-edge coloured undirected bipartite multigraph. The problem formulation would then turn into: Find the set of edges without colour-alternating paths or cycles which has maximum weight sum.

Note 4: I suspect that the problem might be NP-hard, but I am not that experienced with reductions so I haven't managed to prove it yet.

Yet another example:

Imagine you had

4 vertices: {u1, u2} {v1, v2}

4 edges: {u1->v1, u1->v2, u2->v1, v2->u2}

Then, regardless of their weights, u1->v2 and v2->u2 cannot be in the same DirectionalMatching, neither can v2->u2 and u2->v1. However u1->v1 and u1->v2 can, and so can u1->v1 and u2->v1.

回答1:

Define a new undirected graph G' from G as follows.

1. G' has a node (A, B) with weight w for each directed edge (A, B) with weight w in G
2. G' has undirected edge ((A, B),(B, C)) if (A, B) and (B, C) are both directed edges in G

http://en.wikipedia.org/wiki/Line_graph#Line_digraphs

Now find a maximal (weighted) independent vertex set in G'.

http://en.wikipedia.org/wiki/Vertex_independent_set

Edit: stuff after this point only works if all of the edge weights are the same - when the edge weights have different values its a more difficult problem (google "maximum weight independent vertex set" for possible algorithms)

Typically this would be an NP-hard problem. However, G' is a bipartite graph -- it contains only even cycles. Finding the maximal (weighted) independent vertex set in a bipartite graph is not NP-hard.

The algorithm you will run on G' is as follows.

1. Find the connected components of G', say H_1, H_2, ..., H_k
2. For each H_i do a 2-coloring (say red and blue) of the nodes. The cookbook approach here is to do a depth-first search on H_i alternating colors. A simple approach would be to color each vertex in H_i based on whether the corresponding edge in G goes from U to V (red) or from V to U (blue).
3. The two options for which nodes to select from H_i are either all the red nodes or all the blue nodes. Choose the colored node set with higher weight. For example, the red node set has weight equal to H_i.nodes.where(node => node.color == red).sum(node => node.w). Call the higher-weight node set N_i.
4. Your maximal weighted independent vertex set is now union(N_1, N_2, ..., N_k).

Since each vertex in G' corresponds to one of the directed edges in G, you have your maximal DirectionalMatching.

回答2:

This problem can be solved in polynomial time using the Hungarian Algorithm. The "proof" by Vor above is wrong.

The method of structuring the problem for the above example is as follows:

   D E F
A  # 7 9  
B  1 # #
C  # 3 #

where "#" means negative infinity. You then resolve the matrix using the Hungarian algorithm to determine the maximum matching. You can multiply the numbers by -1 if you want to find a minimum matching.