# Randomized Parameterized Algorithms for the Kidney Exchange Problem
## 2 Preliminaries and Problem Definitions
### KEP Definitions  
From the graph theory perspective, the KEP without chains may be modeled as finding a maximum weighted packing of vertex-disjoint cycle in a directed graph \(D=(V,A)\), where each vertex corresponds to an incompatible patient-donor pair consisting of a patient and his incompatible donor, each arc \((i,j)\) represents that the donor of \(i\) is compatible with the patient of \(j\). The weight \(w_{ij}\) of each arc \((i,j)\) represents the collective benefit of the kidney swap between the patient of \(j\) and the donor of \(i\). In kidney exchange without altruistic donors, a donor is willing to donate his kidney if and only if his associated patient receives a kidney. The kidney transplants may proceed in the same cycle of the graph \(D\) because each vertex of the cycle is compatible with the donating kidney of the previous vertex. Thus, when a cycle consists of \(k\) patient-donor pairs, it is called a \(k\)-cycle exchange. Because the length of exchange cycles is restricted for logistical reasons and to avoid risk, for a \(k\)-cycle exchange, \(k\) does not exceed an integer \(L\) (\(2\leq L\leq 5\)). The kidney exchange problem without chains is defined as follows:  
Kidney Exchange Problem without Chains:  
**Input:** Directed graph \(D=(V,A)\), arc weight function \(w:A\to R^{+}\), and positive integer \(L\).  
**Question:** Finding a maximum weighted set of vertex-disjoint cycles with length at most \(L\).  
When \(L=2\), the KEP becomes the maximum weighted matching problem for an undirected graph \(G\), where \(V(G)=V(D)\)[7]. For two vertices \(v_{i},v_{j}\in V(G)\) there is an edge \(\{v_{i},v_{j}\}\in E(G)\) in \(G\) if there are both arc \((v_{i},v_{j})\in A(D)\) and \((v_{j},v_{i})\in A(D)\) in \(D\), and edge weight \(w(\{v_{i},v_{j}\})=w(v_{i},v_{j})+w(v_{j},v_{i})\). Therefore, we can solve the KEP by utilizing the maximum matching algorithm which has running time \(O(|V(G)|(|E(G)|+|V(G)|\log|V(G)|))\)Kidney (2000). If \(L=\infty\) (i.e., there is no upper bound on the maximum length of a cycle), we can transform the KEP into the maximum weight perfect matching problem of a bipartite graph. The bipartite graph \(G=(\{V_{d},V_{p}\},E)\) can be constructed in the following way: if vertex \(v_{i}\in V(D)\) in digraph \(D\), there are a vertex \(v_{id}\in V_{d}\), a vertex \(v_{ip}\in V_{p}\) and an edge \(\{v_{id},v_{ip}\}\in E\) with weight \(w(\{v_{id},v_{ip}\})=0\) in graph \(G\); if arc \((v_{i},v_{j})\in A(D)\) (\(i\
eq j\)) in digraph \(D\), there is an edge \(\{v_{id},v_{jp}\}\in E\) with weight \(w(\{v_{id},v_{jp}\})=w(v_{i},v_{j})\) in graph \(G\). If \(\{v_{id},v_{jp}\}\) is in the maximum weight perfect matching of graph \(G\) and \(i\
eq j\), then \(v_{i}\) and \(v_{j}\) are in the same exchange cycle of \(D\). If \(\{v_{id},v_{ip}\}\) is in the maximum weight perfect matching of graph \(G\), then \(v_{i}\) is not in any exchange cycle of \(D\). Thus, if there is no upper bound on the length of cycles, the KEP can be transformed into the maximum weight perfect matching problem and solved in polynomial time. When \(L\geq 3\), the KEP is NP-hard by reducing from the 3D-matching problem [3; 4].