4
$\begingroup$

Context: I'm modelling kidney exchanges through directed acyclic graphs. I convert these to Bipartite graphs (by splitting each node into a donor and receiver, and the edge from the original graph exist between corresponding donors and receivers). I want a way to find maximum number of edges through disjoint chains and I've been trying to do so through maximum wtd matching.

I know I can use ford-fulkerson to find a maximum wtd perfect matching, however, the main problem I'm facing is that the matchings can only exist for chains beginning with specific vertices. For example, if this is my directed acyclic graph:

enter image description here

Turning this into a Bipartite graph and using the maximum wtd matching way, I get the chain 0->1->3->5->6 but I also get 2->4. However, I can only have chains beginning with 0 so 2->4 should not come up.

I wanted to know if there were any ways to work around this problem? Someone suggested making this a minimum cost perfect matching problem but I'm confused how.

I realise this is a weird question but any help would be appreciated!

$\endgroup$
  • $\begingroup$ If you have just one starting vertex, you can do this quite easily by looking for the longest path in a DAG beginning with that vertex (this is the Critical Path problem -- solvable in linear time using dynamic programming for directed acyclic graphs, but NP-hard for general directed or undirected graphs). If you have more than one, I think you could solve this as a max flow problem: create a new source vertex with capacity-1 edges to each starting vertex, set all existing edges to also have capacity 1, and find the maximum flow. $\endgroup$ – j_random_hacker Jun 20 '18 at 9:38
  • $\begingroup$ Okay so this is in line with what I've been thinking, which is a positive for me, however here are a couple of issues: 1. There can be multiple starting vertices. For example in the graph above I could have a new vertex, say A, which has an edge from A to 3. Then I have two starting points, 0 and A. 2. It's mainly the capacities I'm confused by. For example, when I make my bipartite graph I split the vertices as said above, what should I keep as the capacity for such edges? Should I not have such an edge? In such a max flow problem, does the source only have edges joining the starting nodes? $\endgroup$ – S.walia Jun 20 '18 at 16:26
2
$\begingroup$

To make this a minimum-cost perfect matching problem, split each node as you indicated (sending/receiving). Add a high-cost edge from each node's sending node to its own receiving node. This high-cost edge will only be used if that node does not receive a kidney. Additionally, I assume Node 0 in the above graph is supposed to be an altruistic donor or a deceased organ donor that does not need to receive a kidney. (Otherwise, your example has no cycles and no exchange can take place.) Assuming Node 0 is a 1-way donor, add low cost edges from every sending node to Node 0's receiving node.

Then solve the minimum-cost perfect matching problem. A perfect matching is obviously possible (every sending node can send to its own receiving node). A minimum-cost perfect matching will use as few of the high-cost edges as possible. Minimizing the number of high-cost edges (nodes that send to themselves) is the same as maximizing the number of nodes that receive a kidney.

This is also known as the assignment problem and can be solved in polynomial time. Most kidney-exchange research adds the significant complication of requiring cycles to be at most length k. That complication makes the problem NP-hard. Altruistic donors could allow for longer cycles in practice.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.