# how to maximise the no of edges selected in the graph in form of cycles of unbounded length?

Recently i started looking the perfect cycle cover algorithm related to kidney exchange problem where it is considered as NP-Complete for cycles restricted to a length>2. However if cycles are not restricted by removing the length constraint it is considered as solvable in polynomial time ,But if perfect cycle cover doesn't exist and just we need to maximise the no of edges selected in form of cycles(So as to maximise the no of kidney exchanges), also no restriction on cycle's length, then how do we do it?

I am thinking of finding all cycles in the graph and then one by one remove the cycle's edges from the graph and then find the cycles in the residual graph and so on till no more cycles exist and then sum up all the cycle's lengths continuing this for all cycles and find the solution with maximum edges selected. But since this is not a good solution i want to know how to solve this maximising problem

A solution is to solve the assignment problem. Let's call $$G(W, E)$$ your initial graph and build a weighted bipartite graph $$G'(U,V,E')$$:

• on the first side $$U$$, you have one vertex $$u_i$$ for $$w_i \in W$$. In the kidney exchange analogy they are the donors.
• on the other side $$V$$, you also have one vertex $$v_i$$ for $$w_i \in W$$. In the kidney exchange analogy they are the recipients.

Now, for every $$e \in E$$ linking $$w_1$$ and $$w_2$$, put two edges in $$E'$$:

• $$u_1$$ to $$v_2$$, weight $$0$$
• $$u_2$$ to $$v_1$$, weight $$0$$

Also, for every $$w_i \in W$$, add an extra edge in $$E'$$:
• $$u_i$$ to $$v_i$$, weight $$1$$
These edges represent the possibility to have no cycle for $$w_i$$ in the optimal solution.
Now solve the assignment problem using Hungarian algorithm ($$O(n^3)$$), trying to minimize the edges selected in the assignment. You get the optimal solution maximizing the number of vertex covered by cycles.