# Randomized Parameterized Algorithms for the Kidney Exchange Problem
## 1 Introduction
Recently, some researchers started studying exact exponential algorithms and parameterized algorithms for the KEP. For the maximum cycle weight KEP with \(L=3\), an \(O^{*}(2^{k})\) FPT algorithm [4] was proposed by turning it into a maximum weight matching problem, where \(k\) is the minimum size of an arc set \(S\) where there is at least one arc in \(S\) from each 3-cycle of the instance. However, the problem finding an arc set \(S\) with the minimum size is NP-hard. Recently, [PERSON] and [PERSON] [8] studied the variant of the KEP which contains chain exchanges and allows some compatible patient-donor pairs to participate in exchanges to find better matched kidneys. They designed two \(O(2^{n}n^{3})\) exact algorithms based on dynamic programming and subset convolution for the KEP with and without length constraints, respectively. [PERSON] et al. [23] contracted the representation of a compatibility graph by introducing a way to class the vertices in the graph into different types according to some actual meaning. Based on the number \(k\) of vertex types, [PERSON] and [PERSON] [8] designed an FPT algorithm of running time \(O(2^{O(k^{2})}k^{2k^{2}}+n(n+m))\) for the KEP without length constraints by using decomposition technique. Randomness is an essential resource for solving many computational problems, and randomization is a powerful tool for developing algorithms [24; 25; 26; 27; 28; 29]. Recently, stochastic matching approaches have been applied to deal with the KEP [30; 31]. In fact, stochastic methods can naturally describe many settings of barter exchange problems [32; 33]. Thus, in the future stochastic approaches for the KEP will become an important research issue. In this paper, we study randomized algorithms for the parameterized KEP without chains by the random partitioning technique [24; 25] and the randomized algebraic technique [26; 27; 28; 29]. For ease of description, in what following we use \"KEP\" to refer to the kidney exchange problem without chains. We consider the parameterized KEP involving only 2-cycle and 3-cycle exchanges (namely the case of \(L=3\)), with respect to parameters that correspond to the numbers \(k_{2}\) and \(k_{3}\) of 2-cycle exchanges and 3-cycle exchanges, respectively. We note that the solution \(P\) of a given instance of the KEP involves only 2-cycle and 3-cycle exchanges. Suppose that the vertex set of a given instance can be correctly split into two subsets \(S_{1}\) and \(S_{2}\), where the subset \(S_{1}\) involves only 2-cycle exchanges of \(P\) and the subset \(S_{2}\) involves 3-cycle exchanges of \(P\). Then we can easily find these 2-cycle exchanges in \(S_{1}\) by transforming it into maximum matching problem and find these 3-cycle exchanges in \(S_{2}\) by utilizing an existing 3-set-packing algorithm [34]. Hence, we obtain a parameterized algorithm of running time \(O^{*}(4.6^{3k_{3}}\cdot 2^{2k_{2}})\) by the random partitioning technique. For the case of \(L\geq 3\), we discuss the parameterized KEP with respect to the number \(k\) of possible kidney transplants. Applying the randomized algebraic technique, we reduce the KEP to the multilinear monomial detection problem, and obtain an \(O^{*}(2^{(k+L)}(k+L)^{2}L^{3}n^{L})\) algorithm based on the results of [PERSON] and [PERSON] [27; 28; 29]. This paper is organized as follows. Section 2 covers the preliminaries and notations, and introduces the formal definitions of the KEP without chains. In Sections 3 and 4, we investigate the randomized algorithms for two parameterized models of the KEP, and we present two randomized FPT algorithms. Finally, in Section 5 we give a short summary of our works and some future directions.