# Randomized Parameterized Algorithms for the Kidney Exchange Problem
## 4 A Randomized Algorithm Based on Algebraic Technique
There is a randomized algorithm that on every \(P(X,z)\) runs \(O^{*}(2^{k}t^{2}s(n))\) time, outputs \"\(YES\)\" with high probability if \(Q_{t}(X)\) contains a multilinear monomial of degree at most \(k\), and always outputs \"\(NO\)\" if there is no multilinear monomial of degree at most \(k\) in \(Q_{t}(X)\)._  
Our algorithm for the \(p\)-KEP relies on Lemma 1. For a given directed graph \(D=(V,A)\) of the \(p\)-KEP, we construct a suitable polynomial \(P(X,z)\) such that for a positive integer \(k\), the coefficient of \(z^{k}\) is a polynomial \(Q_{k}(X)\) in the sum-product expansion of \(P(X,z)\), the degree of each monomial in \(Q_{k}(X)\) is \(k\), and each multilinear monomial in \(Q_{k}(X)\) maps to a packing of vertex-disjoint cycle in \(D=(V,A)\). Hence, we can prove that there is a solution set \(S\) of size \(k\) for the \(p\)-KEP if and only if \(Q_{k}(X)\) contains a multilinear monomial of degree \(k\) (see Lemma 2 below). According to the above idea, we first construct a polynomial from the given instance. In a given directed graph \(D=(V,A)\), let vertex set \(V=\{v_{1},v_{2},\cdots,v_{n}\}\), variable set \(X=\{x_{1},x_{2},\cdots,x_{n}\}\) and \(z\) be an extra variable. There is a one-to-one mapping relationship between \(V\) and \(X\) which each vertex \(v_{i}\in V\) is mapped to a product \(zx_{i}\) for \(i=1,\cdots,n\). If \(v_{i_{1}}\cdots v_{i_{j}}v_{i_{1}}\) form a directed cycle \(C\) in graph \(D\), then define a monomial \(\pi(C)=zx_{i_{1}}\cdots zx_{i_{j}}=z^{|V(C)|}x_{i_{1}}\cdots x_{i_{j}}\). In graph \(D\), let \(\mathcal{C}\) denote the cycle set which contains all cycles of length in the range \([2,L]\), and \(\mathcal{C}(v_{i})\) denote a cycle set, each of which passes through vertex \(v_{i}\). For graph \(D\), we partition \(\mathcal{C}\) into \(\mathcal{C}(v_{1}),\mathcal{C}(v_{2}),\cdots,\mathcal{C}(v_{n})\) by the following Partitioning Operation. ```
1:\(\mathcal{C}=\emptyset\);
2:for each \(v_{i}\in V\)do
3: In graph \(D\), find cycle set \(\mathcal{C}(v_{i})\) such that \(\mathcal{C}(v_{i})\) contains all directed cycles of length in \([2,L]\)
4: and each cycle in \(\mathcal{C}(v_{i})\) passes through \(v_{i}\);
5:\(\mathcal{C}=\mathcal{C}\cup\mathcal{C}(v_{i})\);
6:\(D=D[V(D)-\{v_{i}\}]\);
7:endfor
```  
In the Partitioning Operation, we find cycle set \(\mathcal{C}(v_{i})\) by applying [PERSON]'s algorithm for strongly connected components [42]: find a strongly connected component by the depth-first search starting vertex \(v_{i}\) on graph \(D\), where the search depth is at most \(L\), and then find all cycles passing through \(v_{i}\) by the backtracking algorithm. It takes \(O(|V|+|E|)\) time running [PERSON]'s algorithm. By the Partitioning Operation, we obtain \(\mathcal{C}(v_{1}),\mathcal{C}(v_{2}),\cdots,\mathcal{C}(v_{n})\) and \(\mathcal{C}\). We define  
\[p(\mathcal{C}(v_{i}))=\left\{ \begin{array}{ll}1,&\mbox{if }\mathcal{C}(v_{i})= \emptyset;\\ 1+\sum_{\mathcal{C}\in\mathcal{C}(v_{i})}\pi(\mathcal{C}),&\mbox{if }\mathcal{C}(v_{i}) \
eq\emptyset.\end{array} \right. \tag{1}\]  
\[P(\mathcal{C})=\prod_{i=1}^{n}p(\mathcal{C}(v_{i})). \tag{2}\]  
Let \(P(X,z)=P(\mathcal{C})\). If we view \(z\) as an extra indeterminate, the sum-product expansion of \(P(X,z)\) can be expressed as follows:  
\[P(X,z)=1+\sum_{t=1}^{n}Q_{t}(X)z^{t}. \tag{3}\]  
Since each vertex \(v_{i}\in V\) is mapped to a product \(zx_{i}\) (where \(x_{i}\in X\)). From expressions (1) and (2), we know that if in the expansion expression (3) of \(P(X,z)\) there is a term which contains \(z^{k}\), then \(Q_{k}(X)\) is a polynomial, where the degree of each monomial is \(k\). By the polynomial construction, we have the following lemma. Lemma 2: _For a given graph \(D\) of the \(p\)-KEP, there is a solution set \(S\) of size \(k\) if and only if the polynomial \(Q_{k}(X)\) contains a multilinear monomial of degree \(k\)._  
Proof.