Directed maximum weighted bipartite matching allowing sharing of start/end vertices

Question

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.

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