# Randomized Parameterized Algorithms for the Kidney Exchange Problem
## 3 A Randomized Algorithm Based on Random Partitioning Technique  
For the KEP, [PERSON] [5] showed that in a large population, all the gains from exchange can be obtained by using 2-cycle, 3-cycle and 4-cycle exchanges. Especially, 2-cycle and 3-cycle exchanges capture almost all the gains from exchange, and their marginal contribution is significantly large. In practice, 2-cycle and 3-cycle exchanges are typically used, such as in the New England Program [38] and the kidney exchange program of the United Network for Organ Sharing [5]. In this section, we consider the maximum exchange size KEP whose exchanges is limited only 2-cycle and 3-cycle exchanges (namely \(L=3\)). The model is defined as follows:  
Parameterized KEP\({}_{L=3}\) (\(p\)-KEP\({}_{L=3}\)):  
**Input:** a simple directed graph \(D=(V,A)\), and two positive integers \(k_{2}\) and \(k_{3}\);  
**Parameter:**\(k_{2}\) and \(k_{3}\);  
**Question:** Is there a packing of vertex-disjoint cycles in \(D\), comprising at least \(k_{2}\) 2-cycles and at least \(k_{3}\) 3-cycles? Applying random partitioning technique, we design a randomized algorithm for the \(p\)-KEP\({}_{L=3}\). Given an instance \((D,k_{2},k_{3})\) of the \(p\)-KEP\({}_{L=3}\), we stochastically divide the vertex set \(V\) into two subsets \(V_{2}\) and \(V_{3}\) by putting \(v\) into \(V_{2}\) or \(V_{3}\) with probability \(1/2\) for each vertex \(v\in V\). When the instance is a Yes-instance, there exists a proper partition such that \(k_{2}\) 2-cycles are in \(D[V_{2}]\) and \(k_{3}\) 3-cycles are in \(D[V_{3}]\). We can easily find a packing with \(k_{2}\) vertex-disjoint 2-cycles in \(D[V_{2}]\) through transforming into the maximum matching problem of an undirected graph and invoking the corresponding algorithm, and find a packing with \(k_{3}\) vertex-disjoint 3-cycles in \(D[V_{3}]\) by transforming into the 3-set-packing problem and invoking the corresponding algorithm. Algorithm 1 RKEP\((D,k_{2},k_{3})\) is the detailed randomized algorithm of the \(p\)-KEP\({}_{L=3}\) based on the random partitioning technique, where \(c\) is a constant which is applied to adjust the probability that Algorithm RKEP\((D,k_{2},k_{3})\) fails. ```
0: a directed graph \(D=(V,A)\), positive integer \(c\), and two positive integers \(k_{2}\) and \(k_{3}\);
0: a packing of vertex-disjoint cycles in \(D\), comprising at least \(k_{2}\) 2-cycles and at least \(k_{3}\) 3-cycles, otherwise return no solution exists. 1:\(times\leq c\cdot 2^{\text{k}_{3}+2k_{2}}\)do
2:\(times=times+1\);
3:\(V_{2}=V_{3}=\emptyset\);
4:for all\(v\in V\)do
5: put \(v\) into \(V_{2}\) or \(V_{3}\) with probability \(1/2\);
6:endfor
7: for the induced subgraph \(D[V_{2}]\), find a packing \(P_{2}\) of at least \(k_{2}\) vertex-disjoint 2-cycles;
8:if no \(P_{2}\) exists then
9: goto next loop iteration;
10:endif
11:for the induced subgraph \(D[V_{3}]\), find a packing \(P_{3}\) of at least \(k_{3}\) vertex-disjoint 3-cycles;
12:if no \(P_{3}\) exists then
13: goto next loop iteration;
14:endif
15:return\(P_{2}\cup P_{3}\);
16:endwhile
17:return no solution exists;
```  
**Algorithm 1** RKEP\((D,k_{2},k_{3})\)  
**Theorem 1**. : _For the \(p\)-\(\text{KEP}_{L=3}\), there exists a randomized algorithm of running time \(O^{*}(4.6^{3k_{3}}\cdot 2^{2k_{2}})\) which, for any given constant \(c>0\), produces the desired packing in a Yes-instance with probability at least \(1-\frac{1}{c^{2}}\)._  
Proof. : For the \(p\)-\(\text{KEP}_{L=3}\), if an instance \((D,k_{2},k_{3})\) is a No-instance, then no matter how the vertex set \(V\) is split, we cannot find a required packing in \(V_{2}\) and \(V_{3}\). Thus, no solution to the \(p\)-\(\text{KEP}_{L=3}\) will be returned in line 18 of Algorithm \(\text{RKEP}(D,k_{2},k_{3})\). Now assume that the given instance \((D,k_{2},k_{3})\) is a Yes-instance and \(P\) is a solution to the \(p\)-\(\text{KEP}_{L=3}\). Then there are \(k_{2}\) vertex-disjoint 2-cycles and \(k_{3}\) vertex disjoint 3-cycles in \(D[P]\).