# Randomized Parameterized Algorithms for the Kidney Exchange Problem
## 4 A Randomized Algorithm Based on Algebraic Technique  
Efficient kidney exchange can be achieved by 2-cycle and 3-cycle exchange. However, with the progress of technology, cycle exchange with length more than 3 has proved useful in kidney exchange. Limitations on the maximum length of cycles may be weakened in the future. It is reported that a 9-cycle exchange was performed successfully in 2015 [20]. In this section, we discuss the KEP with \(L\geq 3\) parameterized by the size of kidney transplants. The parameterized model is defined as follows:  
Parameterized KEP (\(p\)-KEP):  
**Input:** a simple directed graph \(D=(V,A)\), and a positive integer \(k\);  
**Parameter:**\(k\);  
**Question:** In graph \(D\), is there a packing \(S\) of vertex-disjoint cycles such that \(|V(S)|\geq k\) and the length of each cycle is in the range \([2,L]\)? Here, \(L\) is a fixed integer at least 3. For an integer \(t\) and a packing \(S\), if \(|V(S)|=t\) and \(t\geq k\), then \(S\) is called a solution set of size \(t\) for the \(p\)-KEP. By the above definition, the \(p\)-KEP is a special class of the set packing problem. For the set packing problem, most work has focused on the case that each set has the same size, such as the deterministic time \(O^{*}(2.3^{3k})\) algorithm for the 3-set \(k\)-packing problem [34] and the randomized algorithm with time \(O^{*}(2^{mk})\) for the \(m\)-set \(k\)-packing problem [27]. However, so far relatively little research has been carried out on the set packing problem such as the \(p\)-KEP which the size of each set is limited in a range \([2,L]\). In the section, we develop a randomized algorithm for the \(p\)-KEP based on the algebraic technique, introduced by [PERSON] in [27]. Developed by [PERSON] and [PERSON] [28,29], the randomized algebraic technique has been successfully applied to some graph problems and counting problems [26,40,41]. An outstanding example is the improved algorithm with running time \(O(1.657^{m})\) for the Hamiltonian path problem [26], which resolves the open problem for half of a century whether there exists an \(O(c^{n})\) time algorithm with some constant \(c<2\) for the Hamiltonian path problem. The main idea of the algebraic approach is as follows: By constructing an appropriate multivariate polynomial for a given problem instance, the problem is reduced to the multilinear monomial detection problem for the sum-product expansion of the polynomial represented by a monotone arithmetic circuit, where a monomial \(x_{1}^{i_{1}}x_{2}^{i_{2}}\cdots x_{k}^{i_{k}}\) whose degree is \(\sum_{j=1}^{k}i_{j}\) is called multilinear if each \(i_{j}\)\((1\leq j\leq k)\) is either 0 or 1, and the degree of a polynomial is the maximum degree of all monomials in its expansion. A monotone arithmetic circuit is a directed acyclic graph in which each vertex of in-degree 0 is an input gate labeled either with variable or a non-negative real constant, the other vertices have in-degree 2 and are labeled either \"+\" (addition gates) or \"\(\times\)\" (multiplication gates), and there is exactly one vertex with out-degree 0 which is called output gate. A polynomial is represented by a monotone arithmetic circuit if it can be computed by the output gate of the circuit. The multilinear monomial detection problem is to decide whether a polynomial \(P(X)\) which can be represented by an arithmetic circuit contains a multilinear monomial of degree at most \(k\) in its sum-product expansion. [PERSON] and [PERSON] gave randomized algorithms for multilinear monomial detection problem in [27] and [29], respectively. In [28], they extended their methods and gave Lemma 1 which is rephrased as follows in terms of our notation. **Lemma 1** (see Lemma 1 in [28]). : _Let \(X\) be a variable set, \(z\) be an extra variable, and \(P(X,z)\) be a polynomial represented by a monotone arithmetic circuit of size \(s(n)\). Assume that the sum-product expansion of \(P(X,z)\) is expressed the form \(\sum_{i\in\mathbb{N}}Q_{i}(X)z^{i}\).