# Randomized Parameterized Algorithms for the Kidney Exchange Problem
## 4 A Randomized Algorithm Based on Algebraic Technique
: (\(\Rightarrow\)): For a given instance of the \(p\)-KEP, assume that \(S\) is a solution set of size \(k\) and it is comprised of the vertices in \(s\) mutually vertex-disjoint cycles of length in range \([2,L]\). We use \(\mathcal{C}^{\prime}\) to denote the cycle set and have \(\mathcal{C}^{\prime}\subseteq\mathcal{C}\). Let \(\{C_{i}\}=\mathcal{C}^{\prime}\cap\mathcal{C}(v_{i})\) and \(s_{i}=|V(\{C_{i}\})|\), \(1\leq i\leq n\). By the Partitioning Operation, we know that \(\mathcal{C}(v_{i})\cap\mathcal{C}(v_{j})=\emptyset\) when \(i\
eq j\). Since the cycles in \(\mathcal{C}^{\prime}\) are mutually vertex-disjoint, either \(\{C_{i}\}=\emptyset\) or \(\{C_{i}\}\) has only one cycle \(C_{i}\) of length in range \([2,L]\), we also have \(s_{i}=0\) when \(\{C_{i}\}=\emptyset\) and \(s_{i}=|V(C_{i})|\) when \(C_{i}\) is a cycle. Thus, we have \(\sum_{i=1}^{n}s_{i}=k\). For \(1\leq i\leq n\), let \(p(C_{i})=1\) if \(\{C_{i}\}=\emptyset\), or \(p(C_{i})=\pi(C_{i})\) if \(C_{i}\) is a cycle in \(\mathcal{C}(v_{i})\). It follows from the above definition and expression (1) that \(p(C_{i})\) is a monomial term in \(p(\mathcal{C}(v_{i}))\). Let \(p(\mathcal{C}^{\prime})=\prod_{i=1}^{n}p(C_{i})\). Since the cycles in \(\mathcal{C}^{\prime}\) are mutually vertex-disjoint and \(\sum_{i=1}^{n}s_{i}=k\), \(p(\mathcal{C}^{\prime})=z^{k}q(X)\) where \(q(X)\) is a multilinear monomial of degree \(k\). Hence, by expressions (1), (2) and (3), there is a degree \(k\) multilinear monomial \(q(X)\) in the polynomial \(Q_{k}(X)\). (\(\Leftarrow\)): Assume that there is a monomial of the form \(z^{k}q(X)\) in the sum-product expansion of \(P(X,z)\), where \(q(X)\) is a multilinear monomial of degree \(k\). Obviously, \(q(X)\) is a monomial in \(Q_{k}(X)\). It follows from expressions (1) and (2) that there exists an expression \(z^{k}q(X)=\prod_{i=1}^{n}p_{i}\) (where \(p_{i}\) is corresponding to a term from \(p(\mathcal{C}(v_{i}))\)) such that either \(p_{i}=1\) or \(p_{i}=\pi(C_{i})\) for some cycle \(C_{i}\in\mathcal{C}(v_{i})\). Let \(\mathcal{C}^{\prime}=\{C_{i}|p_{i}\
eq 1,p_{i}=\pi(C_{i}),1\leq i\leq n\}\). Since \(q(X)\) is a multilinear monomial of degree \(k\), the cycles in \(\mathcal{C}^{\prime}\) are mutually vertex-disjoint. Let \(s_{i}\) denote the degree of monomial \(p_{i}\), then \(s_{i}=0\) when \(p_{i}=1\), or \(s_{i}=|V(C_{i})|\) when \(p_{i}\
eq 1\), and \(\sum_{i=1}^{n}s_{i}=k\), namely, \(\sum_{\mathcal{C}\in\mathcal{C}^{\prime}}|V(C)|=k\). By the Partitioning Operation, the length of each cycle in \(\mathcal{C}^{\prime}\) is in the range \([2,L]\). Therefore, the vertex set of \(\mathcal{C}^{\prime}\) is a solution of size \(k\) for the \(p\)-KEP. For the \(p\)-KEP, we require to decide whether there is a packing \(S\) of vertex-disjoint cycles of lengths in the range \([2,L]\) such that \(|V(S)|\geq k\). We can prove the following Lemma 3. Lemma 3: _For a given graph \(D\) of the \(p\)-KEP, if each polynomial \(Q_{i}(X)\) for \(k\leq i\leq k+L-1\) does not contain any multilinear monomial of degree \(i\), then there does not exist a solution \(S\) with \(|V(S)|\geq k\) for the given instance._Proof. : By Lemma 2, we know that there is no solution of size in range \([k,k+L-1]\) if each polynomial \(Q_{i}(X)\) for \(k\leq i\leq k+L-1\) does not contain any multilinear monomial of degree \(i\). Thus, we only prove there is no solution of size at least \(k+L\) by contradiction. Assume that there is a solution \(S\) with \(|V(S)|\geq k+L\) when each polynomial \(Q_{i}(X)\) for \(k\leq i\leq k+L-1\) does not contain any multilinear monomial of degree \(i\). Suppose that \(S\) is comprised of mutually vertex-disjoint cycles \(C_{1},C_{2},\cdots,C_{l}\) of length in range \([2,L]\) and \(S=\{C_{1},C_{2},\cdots,C_{l}\}\). Let \(S_{max<k}\subset S\) be the cycle set whose \(|V(S_{max<k})|\) is maximum and \(|V(S_{max<k})|<k\). Thus, there is a vertex-disjoint cycle set \(S^{\prime}=S_{max<k}\cup\{C_{i}\}\) where \(C_{i}\in S-S_{max<k}\) and \(|V(S^{\prime})|\in[k,k+L-1]\).