title: Directed maximum weighted bipartite matching allowing sharing of start/end vertices
body: <p>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:</p>
  
  <p><img src="https://i.stack.imgur.com/YC0P4.png" alt="bipartite directed and weighted graph"></p>
  
  <p>In this case: </p>
  
  <pre><code>U = {A,B,C} 
  V = {D,E,F} 
  E = {(A-&gt;E,7), (B-&gt;D,1), (C-&gt;E,3), (F-&gt;A,9)} 
  </code></pre>
  
  <p><strong>Definition:</strong> <em>DirectionalMatching</em> (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 <em>DirectionalMatching</em> then V /= U' and V' /= U but it may be that U = U' or V = V'.</p>
  
  <p><strong>My question:</strong> How to efficiently find a <em>DirectionalMatching</em>, as defined above, for a bipartite directional weighted graph which maximizes the sum of the weights of its edges? </p>
  
  <p>By <em>efficiently</em>, I mean polynomial complexity or faster, I already know how to implement a naive brute force approach.</p>
  
  <p>In the example above the maximum weighted <em>DirectionalMatching</em> is: {F->A,C->E,B->D}, with a value of 13.</p>
  
  <p>Formally demonstrating the equivalence of this problem to any other well known problem in graph theory would also be valuable.</p>
  
  <p>Thanks!</p>
  
  <p><strong>Note 1:</strong>  This question is based on <a href="https://stackoverflow.com/questions/14824320/maximum-weighted-bipartite-matching-with-directed-edges">Maximum weighted bipartite matching _with_ directed edges</a> 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.</p>
  
  <p><strong>Note 2:</strong> This is a maximum <strong>weight</strong> 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.</p>
  
  <p><strong>Note 2:</strong> During my research to solve the problem I found this paper, I think it would be helpful to others trying to find a solution: <a href="http://www.cs.rhul.ac.uk/~gutin/paperstsp/alt.pdf" rel="nofollow noreferrer">Alternating cycles and paths in edge-coloured
  multigraphs: a survey</a></p>
  
  <p><strong>Note 3:</strong> 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: <em>Find the set of edges without colour-alternating paths or cycles which has maximum weight sum.</em></p>
  
  <p><strong>Note 4:</strong> 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.</p>
  
  <p><strong>Yet another example</strong>: </p>
  
  <p>Imagine you had </p>
  
  <p>4 vertices: <code>{u1, u2}</code> <code>{v1, v2}</code> </p>
  
  <p>4 edges: <code>{u1-&gt;v1, u1-&gt;v2, u2-&gt;v1, v2-&gt;u2}</code> </p>
  
  <p>Then, regardless of their weights, <code>u1-&gt;v2</code> and <code>v2-&gt;u2</code> cannot be in the same <em>DirectionalMatching</em>, neither can <code>v2-&gt;u2</code> and <code>u2-&gt;v1</code>. However <code>u1-&gt;v1</code> and <code>u1-&gt;v2</code> can, and so can <code>u1-&gt;v1</code> and <code>u2-&gt;v1</code>.</p>