# 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!

• 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. Jun 20, 2018 at 9:38
• 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? Jun 20, 2018 at 16:26