StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

PODirected maximum weighted bipartite matching allowing sharing of start/end vertices
text
Body
copied!<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->E,7), (B->D,1), (C->E,3), (F->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->v1, u1->v2, u2->v1, v2->u2}</code> </p> <p>Then, regardless of their weights, <code>u1->v2</code> and <code>v2->u2</code> cannot be in the same <em>DirectionalMatching</em>, neither can <code>v2->u2</code> and <code>u2->v1</code>. However <code>u1->v1</code> and <code>u1->v2</code> can, and so can <code>u1->v1</code> and <code>u2->v1</code>.</p>

Querying!

Guidance

An individual column

Larger individual text columns get their own page to allow for proper reading.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload