How can I find matchings in a Bipartite graph beginning with specific vertices?

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:

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!

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.

StackExchange Computer Science Q#93239, answer score: 2