0
$\begingroup$

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

$\endgroup$

1 Answer 1

0
$\begingroup$

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$

They represent the potential trade.

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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