Parameterized Algorithms for Kidney Exchange

1 Introduction

Patients having acute renal failures are typically treated either with dialysis or with kidney transplantation. However, the quality of life on dialysis is comparitively lower and also the average life span of the patients on dialysis is around 10 years. For this reason, most patients prefer a kidney transplantation over periodic dialysis. However, the gap between the demand and supply of kidneys, which can be obtained either from a deceased person or from a living donor, is so large that the average waiting time varies from 2 to 5 years at most centers. Moreover, even if a patient is able to find a donor, there could be many medical reasons (like blood group or tissue mismatch) due to which the donor could not donate his/her kidney to the patient.

The Kidney Paired Donation (KPD), a.k.a Kidney Exchange program, allows donors to donate their kidneys to compatible other patients with the understanding that their patients will also receive medically compatible kidneys thereby forming some kind of barter market [Alvin Roth, Tayfun S¨onmez, Utku ¨Unver, 2004; Alvin Roth, Tayfun S¨onmez, Utku ¨Unver, 2007; Abraham et al., 2007]. Since its inception in [Rapaport, 1986], an increasing amount of people register in the kidney exchange program since, this way, patients not only have a better opportunity to receive compatible kidneys, but also can get medically better matched kidneys which last longer [Segev et al., 2005]. The central problem in any kidney exchange program, also known as the clearing problem, is how to transplant kidneys among various patients and donors so that a maximum number of patients receive kidneys.

Typically, kidney exchange happens in a cyclical manner. The problem is represented as a directed graph: a patient along with his/her donor is a vertex; we add directed edges from a vertex u to all other vertices whose patients are compatible with the donor of the vertex u. In a (directed) cycle, the patient of every vertex receives a kidney from the donor of the previous vertex along the cycle. Donors do not have any legal obligation to donate kidneys and thus, technically speaking, a donor can leave the program as soon as his/her corresponding patient receives a kidney [Alvin Roth, Tayfun S¨onmez, Utku ¨Unver, 2005b; Segev et al., 2005]. This is not only unfair but also leaves a patient without any donor. To avoid this problem, all kidney transplantations along a cycle are done simultaneously. As each transplantation involves two surgeries, logistic and human resource constraints allow only a few surgeries to be carried out simultaneously. For this reason, most kidney exchange platforms allow transplantation along cycles of very small length only [Alvin Roth, Tayfun S¨onmez, Utku ¨Unver, 2005b; Abraham et al., 2007; Manlove and O'malley, 2015].

Sometimes we have altruistic donors (a.k.a non-directed donors (NDDs)) who do not have patients paired with them. This allows us to have kidney transplantations along with chains (directed paths) also starting from some altruistic vertices - an altruistic donor donates his/her kidney to some compatible patient whose paired donor donates his/her kidney to the next patient along the chain and so on. Some platform allows non-simultaneous surgeries along a chain since a broken chain is less harmful than a broken cycle - it does not leave any patient without donor [Ross Anderson and Roth, 2015]. However, broken chains also lead to unfairness and thus platforms usually only allow small chains for transplantation. Thus, in the presence of altruistic donors, the fundamental problem of kidney exchange becomes the following: find a collection of disjoint cycles and chains starting from altruistic vertices which covers a maximum number of non-altruistic vertices. We refer to Definition 1 in Section 2 for formal definition of the kidney exchange problem.

1.1 RelatedWork

To the best of our knowledge, [Rapaport, 1986] first introduced the idea of kidney exchange. Since then, many variants and properties have been explored [Alvin Roth, Tayfun S¨onmez, Utku ¨Unver, 2005b; Alvin Roth, Tayfun S¨onmez, Utku ¨Unver, 2005a; Segev et al., 2005]. For example, a line of research allow only cycles [Constantino et al., 2013; Klimentova et al., 2014; S¨onmez and ¨Unver, 2014] while others allow kidney exchange along both cycles and chains [Manlove and O'malley, 2015; Glorie et al., 2014; Xiao and Wang, 2018]. All versions of the kidney exchange problem can be formulated as some suitable version of the graph packing problem. [Jia et al., 2017] discussed interesting relationship between barter market and set packing.

[Krivelevich et al., 2007; Abraham et al., 2007] showed that the basic kidney exchange problem along with its various incarnations are NP-hard. [Krivelevich et al., 2007; Jia et al., 2017] developed approximation algorithms for the kidney exchange problem by exploiting interesting connection with the set packing problem. Practical heuristics and integer linear programming based algorithms haven been extensively explored for the kidney exchange problem [Manlove and O'malley, 2015; Dickerson et al., 2016; Glorie et al., 2014; Li et al., 2014; Biro et al., 2009; Klimentova et al., 2014]. [Dickerson et al., 2016] introduced the notion of "vertex type" and showed its usefulness as a graph parameter in realworld kidney exchange instances. Two vertices is said to have the same vertex type if their neighbourhoods are the same.

The closest predecessor of our work is by [Xiao and Wang, 2018]. They proposed an exact algorithm with running time O(2nn3 ) where n is the number of vertices in the underlying graph. They also presented a fixed parameter tractable algorithm for the kidney exchange problem parameterized by the number of vertex types if we do not have any restriction on the length of cycles and chains. [Lin et al., 2019] studied the version of the kidney exchange problem which allows only cycles and developed a randomized parameterized algorithm with respect to the parameter being (number of patients receiving a kidney, maximum allowed length of any cycle).

1.2 Contribution

Designing exact algorithms for KIDNEY EXCHANGE has been a research focus in algorithmic game theory. We contribute to this line of research in this paper. Our specific contributions are the following.

We design FPT algorithms for the KIDNEY EXCHANGE problem parameterized by the number of patients receiving kidneys [Theorem 1], treewidth of the underlying graph +

maximum length of path(ℓp) + maximum length of cycle allowed (ℓc) [Theorem 3], and the number of vertex types when ℓp ≤ ℓc [Theorem 4]. We also show that the optimization version of the KIDNEY EXCHANGE problem is a linear extended monadic second-order (EMS) extremum problem when max{ℓp, ℓc} = O(1) [Theorem 2].

We show that KIDNEY EXCHANGE admits a polynomial kernel with respect to the number of patients receiving kidneys + maximum degree when max{ℓp, ℓc} is a constant [Theorem 5]. We complement this result by showing that KIDNEY EXCHANGE does not admit any polynomial kernel parameterized by the number of patients receiving kidneys+maximum degree+max{ℓp, ℓc} unless NP ⊆ co - NP/poly [Theorem 6].

Finally, we also design a ( 16 9 +ϵ)-approximation algorithm for KIDNEY EXCHANGE if only cycles of length at most 3 are allowed (and no paths are allowed) [Corollary 1]. We believe that our work substantially improves the current theoretical understanding of the KIDNEY EXCHANGE problem.

1.3 Motivation for the Parameters

Our primary motivation for considering treewidth, max{ℓp, ℓc} and number of patients receiving kidneys as parameters is to have a faster algorithm than the existing O(2n ) time algorithm from [Xiao and Wang, 2018]. Most of our parameters are typically much smaller than the graph's total number of vertices (n).

Whether a donor can donate their kidney to a patient depends on a few health parameters like blood/tissue compatibility, etc. Usually, these parameters can only take a few different values. Due to this reason, the number of vertex types is typically small. [Dickerson et al., 2016] observed this phenomenon in real-world instances of kidney exchange. Hence, this parameter is useful for practical applications.

2 Preliminaries

For an integer k, we denote the sets {0, 1, . . . , k} and {1, 2, . . . , k} by [k]0 and [k] respectively.

A kidney exchange problem is formally represented by a directed graph G = (V,A) which is known as the compatibility graph. A subset B ⊆ V of vertices denotes altruistic donors (also called non-directed donors); the other set V \ B of vertices denote a patient-donor pair who wish to participate in the kidney exchange program. We have a directed edge (u, v) ∈ A if the donor of the vertex u ∈ V has a kidney compatible with the patient of the vertex v ∈ V \ B. Kidney exchange happens either (i) along a trading-cycle u1, u2, . . . , uk where the patient of the vertex ui ∈ V \ B receives a kidney from the donor of the vertex ui-1 ∈ V \ B for every 2 ≤ i ≤ k and the patient of the vertex u1 receives the kidney from the donor of the vertex uk, or (ii) along a trading-chain u1, u2, . . . , uk where u1 ∈ B, ui ∈ V \ B for 2 ≤ i ≤ k and the patient of the vertex uj receives a kidney from the donor of the vertex uj-1 for 2 ≤ j ≤ k. Due to operational reasons, all the kidney transplants along a tradingcycle or a trading-chain should be performed simultaneously. This puts an upper bound on the length ℓ of feasible tradingcycles and trading-chains. We define the length of a path or cycle as the number of edges in it. The kidney exchange clearing problem is to find a collection of feasible tradingcycles and trading-chains which maximizes the number of patients who receive a kidney. Formally it is defined as follows.

Definition 1 (KIDNEY EXCHANGE). Given a directed graph G = (V,A) with no self-loops, an altruistic vertex set B ⊂ V, two integers ℓp and ℓc denoting the maximum length of respectively paths and cycles allowed, and a target t, compute if there exists a collection C of disjoint cycles of length at most ℓc and paths with starting from altruistic vertices only each of length at most ℓp which cover at least t non-altruistic vertices. We denote an arbitrary instance of KIDNEY EXCHANGE by (G, B, ℓp, ℓc, t).

2.1 Graph Theoretic Terminologies

In a graph G, V[G] denotes the set of vertices in G and E[G] denotes the set of edges in G. G[V ′ ] denotes the induced subgraph on V ′ where V ′ ⊆ V[G]. Two vertices u and v in a directed graph G are called vertices of the same type if they have the same set of in-neighbors and the same set of out-neighbors. If there are no self loops in G, vertices of the same type form an independent set. Treewidth measures how treelike an undirected graph is. We refer to [Cygan et al., 2015] for an elaborate description of treewidth, tree decomposition, and nice tree decomposition. Since our graph is directed, whenever we mention treewidth of our graph, we refer to the treewidth of the underlying undirected graph; two vertices u and v are neighbors of the underlying undirected graph if and only if either there is an edge from u to v or from v to u. Also refer to the Table 1 for the important notations.

2.2 Standard Definitions

Due to space constraints we refer the reader to the full version of our paper [Maiti and Dey, 2021] for the formal introduction of Parameterized Complexity and for the definitions of kernalization, cross composition, X3C′ problem and 3-SET PACKING problem. For a detailed discussion on extended monadic second-order extremum problems, please refer to [Arnborg et al., 1991].

3 Results

We present our results in this section. Due to space constraints, we have omitted few proofs. They are marked by (⋆) and they are available in the full version of our paper [Maiti and Dey, 2021].

We begin with presenting an FPT algorithm for the KIDNEY EXCHANGE problem parameterized by the number of patients who receive a kidney. We use the technique of color coding [Alon et al., 1995] to design our algorithm.

Theorem 1. There is a algorithm for the KIDNEY EXCHANGE problem which runs in time O∗ (2O(t) ).

Proof. Let (G, B, ℓp, ℓc, t) be an arbitrary instance of KIDNEY EXCHANGE. If ℓp ≥ t, we check whether there exists a path starting from an altruistic vertex of length t; if ℓc ≥ t, then we check whether there exists a cycle of length ℓ1 for some t ≤ ℓ1 ≤ ℓc. Note that this can be checked by a deterministic algorithm in time O∗ (2O(t) ) (for path see [Cygan et al., 2015], for cycle see [Zehavi, 2016]). If there exists such a cycle or path then clearly (G, B, ℓp, ℓc, t) is a YES instance. So for the rest of the proof , let us update lp and lc as min{ℓp, t - 1} and min{ℓc, t - 1} respectively.

We observe that if (G, B, ℓp, ℓc, t) is a YES instance, then there is a collection C = (D1, . . . ,Dk) of k ≤ t disjoint cycles and paths starting from altruistic vertices each of length at most ℓc and ℓp respectively which covers t1 nonaltruistic vertices where t ≤ t1 ≤ 2t. Note that such a collection will exist as ℓc < t and ℓp < t. We observe that the total number of vertices involved in D1, . . . ,Dk is at most 3t (at most one altruistic vertex in each Di, i ∈ [k]). We color each vertex of G uniformly at random from a set S of 3t colors. We say a coloring of G is good if every vertex in the C gets a different color. A random coloring is good with probability at least

Let C be a non-empty set of colors. Let GC denote an induced subgraph of G on the set of vertices colored with one of the colors in C. We now solve the KIDNEY EXCHANGE problem using dynamic programming. We maintain a dynamic programming table D which is indexed by a set of colors C and a number t′ . D(C, t′ ) denotes whether there is a collection of disjoint cycles and paths starting from altruistic vertices each of length at most ℓc and ℓp respectively which covers t′ non-altruistic vertices in the graph GC and no two vertices in this collection have the same color. Now we introduce a function f which has a set of colors C' and a number i as its arguments. f(C ′ , i) decides whether there is a valid colourful cycle or path starting from altruistic vertex of length i in GC′ . By valid colourful cycle (resp. path) we mean that no two vertices in the cycle (resp. path) have the same color and the length of the cycle (resp. path) is at most ℓc (resp. ℓp). f(C ′ , i) can be computed in time O∗ (2O(i) ) time ( see [Cygan et al., 2015] ). Now we present a recursive formula to compute each entry of the table.

For base cases, let D(C, 0) = 1 and D(∅, t′ ) = 0 if t′ > 0. Now argue the correctness of the above recursive equation. In one direction, let D(C, t′ ) = 1. It implies that there is a collection of valid colourful disjoint cycles and paths starting from altruistic vertices which covers t′ non-altruistic vertices in the graph GC. Now consider once such disjoint cycle or path. Let the number of non-atruistic vertices in it be i and the set of colors of the vertices in it be C ′ . Then clearly f(C ′ , i) = 1 and D(C \C ′ , t-i) = 1. In the other direction, let there exist a set C ′ ⊆ C and a number i ∈ [t′ ] such that D(C \ C ′ , t′ - i) ∧ f(C ′ , i) = 1. This implies that there is a collection of valid colourful disjoint cycles and paths starting from altruistic vertices which covers t′ - i non-altruistic vertices in the graph GC\C′ and there is a valid colourful cycle or path starting from altruistic vertex of length i in GC′ . Hence there is a collection of valid colourful disjoint cycles and paths starting from altruistic vertices which covers t′ nonaltruistic vertices in the graph GC. Therefore D(C, t′ ) = 1.

If (G, B, ℓp, ℓc, t) is a YES instance and coloring is good then ∨ t≤t′≤2t D(S, t′ ) = 1. For a NO instance,

The total number of entries in the table D is 2O(t) · t. Each entry can be computed in time O∗ (2O(ℓ) ). Hence, with probability at least e-3t , our algorithm outputs the correct decision in O∗ (2O(t) ) time. By repeating O(e3t ) times, we find the correct decision with constant probability. The overall running time of our algorithm is O∗ (2O(t) ). The algorithm can be derandomized by using a (n, 3t, 3t)- splitter.

We now consider the parameter treewidth to design an FPT algorithm. Towards that, we first show the following.

Theorem 2 (⋆). The optimization version of the KIDNEY EXCHANGE problem is a linear extended monadic secondorder (EMS) extremum problem when max{ℓp, ℓc} = O(1).

It follows immediately from Theorem 2 and [Arnborg et al., 1991] that KIDNEY EXCHANGE is FPT parameterized by τ ( treewidth ) and ℓ = max{ℓp, ℓc}. However, the running time that we get is not practically useful. Next we proceed to design an efficient dynamic programming based algorithm with running time O∗ (ℓO(τ) τ O(τ) ).

Theorem 3 (⋆). There is an algorithm for the KIDNEY EXCHANGE problem which runs in time O∗ (ℓO(τ) τ O(τ) ).

Proof Sketch. Let (G, B, ℓp, ℓc, t′ ) be an arbitrary instance of KIDNEY EXCHANGE. Let us assume for the rest of proof that ℓc = ℓp for the sake of simplicity. The proof can be easily extended to the case where ℓc ̸= ℓp. Let T = (T, {Xt ⊆ V[G]}t∈V (T)) be a nice tree decomposition of the input nvertex graph G that has width at most τ and has introduce edge nodes. Let T be rooted at some node r. For a node t of T , let Vt be the union of all the bags present in the subtree of T rooted at t, including Xt. Let Gt = (Vt,Et = {e : e is introduced in the subtree rooted at t}) be a subgraph of G[Vt]. We solve the KIDNEY EXCHANGE problem using dynamic programming. At every bag of the tree decomposition, we maintain a dynamic programming table D which is indexed by the tuple (u, (Pi)i∈[µ]0 , (Qi)i∈[µ], (Ei)i∈[µ], g : [µ] → {p, c},L : [µ] → [ℓ]0, a : [µ] → {0, 1}, s : [µ] → Xu ∪ {⊥}, e : [µ] → Xu ∪ {⊥}) where u is the node in the tree decomposition, µ ∈ [τ + 1], (Pi)i∈[µ]0 is a partition of Xu, Qi is a permutation of Pi, and Ei is a set of edges from E[Gu] having both their end points in Pi for every i ∈ [µ]. Here ⊥ is a special symbol which is not part of V[G]. We define D(u, (Pi)i∈[µ]0 , (Qi)i∈[µ], (Ei)i∈[µ], g, L, a, s, e) to be the maximum number of edges present in any subgraph H of Gu such that all the following conditions hold.

• H excluding the isolated vertices is a collection of disjoint paths and disjoint cycles of length at most ℓ.
• Disjoint paths which do not have a vertex from Xu must begin with an altruistic vertex.
• V[H] ∩Xu =Xu \ P0
• For each path P ∈ H, if ∃i, j ∈ [µ] such that Pi ∩ V[P] ̸= ∅ and Pj ∩ V[P] ̸= ∅ then i = j.
• For each cycle C ∈ H, if ∃i, j ∈ [µ] such that Pi ∩ V[C] ̸= ∅ and Pj ∩ V[C] ̸= ∅ then i = j.
• For every i ∈ [µ], if g(i) = p, then either Pi consists of a only one vertex which is isolated or E[H] ∩ E[Gu[Pi]] ⊆ E[P ] where P is a disjoint path in H, Qi is a topological order of Pi w.r.t. P , Ei = E[H] ∩ E[Gu[Pi]], P has L(i) edges and exactly a(i) altruistic vertex. If s(i) =⊥ then starting vertex of P is not part of Pi. If s(i) = v then starting vertex of P is v where v ∈ Pi. If e(i) =⊥ then ending vertex of P is not part of Pi. If e(i) = v then ending vertex of P is v where v ∈ Pi.
• For every i ∈ [µ], if g(i) = c and Qi = x1 > · · · > xν, then E[H] ∩ E[Gu[Pi]] ⊆ E[C] where C is a disjoint cycle in H, Qi is a topological order of Pi w.r.t. the path created by removing the edge (xν, x1) from C, Ei = E[H] ∩ E[Gu[Pi]], C has L(i) edges.

Clearly D(r, ∅, ∅, ∅, ∅, ∅, ∅, ∅, ∅) ≥ t iff (G, B, ℓp, ℓc, t) is a YES instance.

We now explain how we update the table entry D(u, (Pi)i∈[µ]0 , (Qi)i∈[µ], (Ei)i∈[µ], g,L, a, s, e). First, we make the table entry -∞ if we encounter a DP table index which can't lead to a feasible solution. We now use the following formulas to compute table entries in a bottom-up fashion.

Leaf node: Since the tree-decomposition (T , {Xu}u∈V[T ]) is nice, for every leaf node u of T , we have Xu = ∅ and thus all the DP table entries at u is set to 0.

Introduce vertex node: Let u ∈ T be an introducevertex-node with child u′ ∈ T such that Xu = Xu′ ∪ {w} for some vertex w ∈ V[G] \ Xu′ . Since no edge is introduced in an introduce-vertex-node, w is an isolated vertex in Gu. We set the table entry D(u, (Pi)i∈[µ]0 , (Qi)i∈[µ], (Ei)i∈[µ]g, L, a, s, e) to D(u′ , (Pj \ {w}, (Pi)i∈[µ]0\{j}), (Qi)i∈[µ], (Ei)i∈[µ]g, L, a, s, e) if w ∈ Pj where j = 0 or Pj = {w}, g(j) = p, L(j) = 0, s(j) = {w}, e(j) = {w}, a(j) = 1(w ∈ B) where 1(·) is the indicator function otherwise we set it to -∞.

Introduce edge node: Let u ∈ T be an introduce-edgenode introducing an edge (x, y) ∈ E[G] and u′ the child of u. That is, we have Xu = Xu′ . For the table entry D(u, (Pi)i∈[µ]0 , (Qi)i∈[µ], (Ei)i∈[µ], g,L, a, s, e), if any of the following conditions hold

• There does not exist any i ∈ [µ] such that x, y ∈ Pi
• There exists an i ∈ [µ] such that x, y ∈ Pi and (x, y) /∈ Ei

then we set the entry to D(u′ , (Pi)i∈[µ]0 , (Qi)i∈[µ], (Ei)i∈[µ], g, L, a, s, e). Otherwise, let us assume that there exists a j ∈ [µ] such that x, y ∈ Pj and (x, y) ∈ Ej . Intuitively, we compute the appropriate DP table indices at node u′ that we can get when we remove the edge {x, y} from the current DP table index at node u. Then we choose the maximum value among the DP table entries corresponding to DP table indices at node u′ that we computed and add 1 to it to get the value for the current table entry.

Forget vertex node: Let u ∈ T be a forget node with a child u′ such that Xu = Xu′ \ {w} for some w ∈ Xu′ . In this case, we update the table entry D(u, (Pi)i∈[µ]0 , (Qi)i∈[µ], (Ei)i∈[µ], g, L, a, s, e) as follows. For an index of the DP table at node u′ , we define a function DEL(.). Intuively, applying DEL(.) on a DP table index at node u′ leads to a DP table index at node u that we get when we remove w from the DP table index at node u′ .

Join node: For a join node u, let u1, u2 be its two children. Note that Xu = Xu1 = Xu2 . Now we introduce the notion of compatibility. Inituitively, we say that the following pair of tuple ((u1, (P 1 i )i∈[µ1]0 , (Q1i )i∈[µ1], (E1 i )i∈[µ1], g1 , L1 , a1 , s1 , e1 ), (u2, (P 2 i )i∈[µ2]0 , (Q2i )i∈[µ2], (E2 i )i∈[µ2], g2 , L2 , a2 , s2 , e2 )) is said to be compatible with the current DP table index (u, (Pi)i∈[µ]0 , (Qi)i∈[µ], (Ei)i∈[µ], g,L, a, s, e) if partitions in the pair of tuples can be used to construct the current DP table index at node u. For instance, we check whether we can use the paths corresponding to the partitions in the pair to construct the paths corresponding to the partition in the current DP table index at node u.

Let T C be the set of all pair of tuples (T1, T2) which are compatible as per the above conditions with respect to (u, (Pi)i∈[µ]0 , (Qi)i∈[µ], (Ei)i∈[µ], g, L, a, s, e). Then

Each table entry can be updated in ℓO(τ) τ O(τ) time and the size of each table in any node of the tree decomposition is ℓO(τ) τ O(τ) . Hence, the running time of our algorithm is O∗ (ℓO(τ ) τ O(τ ) ).

Let θ denote the number of vertex types in a graph G(V, E). [Xiao and Wang, 2018] presented an FPT algorithm parameterized by θ when ℓp = ℓc = |V|. We now improve the result by presenting our FPT algorithm parameterized by θ when ℓp ≤ ℓc. Towards that, we first present an important lemma on the structure of an optimal solution.

Lemma 1 (⋆). In every KIDNEY EXCHANGE problem instance when ℓp ≤ ℓc, there exists an optimal solution where the length of every path and cycle in that solution is at most θ + 3.

We use the following useful result by Lenstra to design our FPT algorithm.

Lemma 2 (Lenstra's Theorem [Lenstra Jr, 1983]). There is an algorithm for computing a feasible as well as an optimal solution of an integer linear program which is fixed parameter tractable parameterized by the number of variables.

Theorem 4. There exists an FPT algorithm for the KIDNEY EXCHANGE problem parameterized by θ when ℓp ≤ ℓc.

Proof. Let (G = (V, E), B, ℓp, ℓc, t) be an arbitrary instance of KIDNEY EXCHANGE where ℓp ≤ ℓc. We denote the set of types in G by Γ and the type of vertex v by γ(v). For a type γ ∈ Γ, let the set of vertices of type γ be Vγ ⊆ V. If there is a γ ∈ Γ such that Vγ contains both altrusitic and non-altruistic vertices, then we remove the non-altruistic vertices as they have in degree 0 and can't be part of any feasible solution. For a path/cycle p = v1 . . . vk, "signature of p" is defined as γ(v1) . . . γ(vk) and we denote it by γ(p). For a type γ ∈ Γ, we denote the number of vertices of type γ in G by n(γ). For a type γ ∈ Γ and a path/cycle/signature-sequence p, we denote the number of vertices of type γ in p by np(γ). For a path/cycle/signature-sequence p, we denote the number of non-altruistic vertices in p by λ(p). Let A denote the set of signatures of paths starting from altruistic vertices of length at most min{θ + 4, ℓp} and signatures of cycles of length at most min{θ + 3, ℓc} in G. Since there are θ types, we have |A| = O(θθ ). We can compute the set A in time O∗ (θθ ) as follows. For each possible signature-sequence p = γ1 . . . γk of a path, we check if there is an edge from a vertex in Vγi to a vertex in Vγi+1 for all i ∈ [k - 1] and np(γ) ≤ n(γ) for all γ ∈ Γ. If the conditions hold true, then we add p to the set A. Similarly for each possible signature-sequence p = γ1 . . . γk of a path, we check if there is an edge from a vertex in Vγi to a vertex in Vγ(i mod k)+1 for all i ∈ [k] and np(γ) ≤ n(γ) for all γ ∈ Γ. If the conditions hold true, then we add p to the set A.

We consider the following integer linear program; its variables are x(p) for every p ∈ A.

We claim that the KIDNEY EXCHANGE instance is a YES instance if and only if the optimal value of the above ILP is at least t.

In one direction, suppose the KIDNEY EXCHANGE instance is a YES instance. Let C be an optimal solution (a multi-set of paths and cycles) of the KIDNEY EXCHANGE

instance. For signature sequence p ∈ A, we define x(p) = ∑q∈C 1(p = γ(q)) where 1(·) is the indicator function. As C is a subgraph of G, we have ∑p∈A np(γ) ∑q∈C 1(p = γ(q)) ≤ n(γ), ∀γ ∈ Γ. Hence x(p)p∈A is a feasible solution. Since C covers at least t non-altruistic vertices, it follows that ∑p∈A λ(p)x(p) ≥ t. Hence the optimal value of the above ILP is at least t.

On the other direction, suppose there exists a solution (x∗ (p))p∈A to the ILP such that ∑p∈A λ(p)x∗ (p) ≥ t. We now describe an iterative approach to construct a solution C for the KIDNEY EXCHANGE instance from (x∗ (p))p∈A. We initialize C to the empty set and initialize x′ (w) to 0 for all w ∈ A. Let nC(γ) denote the number of vertices of type γ in C. Till there exists a w ∈ A such that x′ (w) < x∗ (w), we add to C a path/cycle q of signature w belonging to G \ C and increase x′ (w) by 1. Now we show that if there exists a w ∈ A such that x′ (w) < x∗ (w), then there is always a path/cycle q of signature w in G \ C. Due to the way A is defined and the fact that w ∈ A, it suffices to show that nw(γ) ≤ n(γ) - nC(γ), ∀γ ∈ Γ. Since (x∗ (p))p∈A is a feasible solution, ∑p∈A np(γ)x∗ (p) ≤ n(γ), ∀γ ∈ Γ. Therefore nw(γ) ≤ ∑p∈A np(γ)(x∗ (p) - x′ (p)) ≤ n(γ) - ∑p∈A np(γ)x′ (w) = n(γ) - nC(γ), ∀γ ∈ Γ. Hence there is always a path/cycle q of signature w. Now when the iterative procedure terminates, the number of non-altruistic vertices covered by C is ∑p∈A λ(p)x∗ (p) which is at least t. Hence, the KIDNEY EXCHANGE instance is a YES instance. Now the result follows from Lemma 2.

We now present our parameterized hardness result. Our parameter is ∆ + ℓp + ℓc. It turns out that the proof of [Abraham et al., 2007, Theorem 1] which shows NP-completeness of the kidney exchange problem can be appropriately modified to get Observation 1. We use X3C′ problem for that which is known to be NP-complete [Gonzalez, 1985].

Observation 1 (⋆). The KIDNEY EXCHANGE problem, parameterized by ∆ + ℓp + ℓc, is para-NP-hard.

We now present our result on kernelization. We show that the KIDNEY EXCHANGE problem admits a polynomial kernel for the parameter t +∆ for every constant ℓp and ℓc.

Theorem5 (⋆). For the KIDNEY EXCHANGE problem, there exists a vertex kernel of size O(t∆max{ℓp,ℓc} ).

Theorem 5 raises the following question: does the KIDNEY EXCHANGE problem admit a polynomial kernel parameterized by t + ∆ + ℓp + ℓc? We answer this question negatively in Theorem 6 using cross composition.

Theorem 6 (⋆). KIDNEY EXCHANGE does not admit any polynomial kernel with respect to the parameter t+∆+ℓp+ℓc unless NP ⊆ co - NP/poly.

We now present our approximation result for the KIDNEY EXCHANGE problem when only cycles of length at most 3 are allowed; no path is allowed. [Biro et al., 2009] studied this problem with the name MAX SIZE ≤3-WAY EXCHANGE and proved APX-hardness. A trivial extension from the result onMAXCYCLEWEIGHT≤k-WAY EXCHANGE in [Biro et al., 2009] leads to a 2+ε approximation algorithm for MAX SIZE ≤3-WAY EXCHANGE. Now towards designing the approximation algorithm, we use the following result for 3SET PACKING problem which is due to [Cygan, 2013].

Lemma 3. For every ε > 0, there is (4/3+ε)-approximation algorithm for the 3-SET PACKING problem for optimizing k.

The following result relates MAX SIZE ≤3-WAY EXCHANGE to 3-SET PACKING.

Theorem 7 (⋆). If there is a α-approximation algorithm for 3-SET PACKING problem, then there is a 4α 3 -approximation algorithm for MAX SIZE ≤3-WAY EXCHANGE.

Theorem 7 immediately gives us the following corollary.

Corollary 1. For every ε > 0, there is a ( 16 9 + ε)- approximation algorithm for KIDNEY EXCHANGE if only cycles of length at most 3 are allowed (and no paths are allowed).

4 Conclusion and Open Questions

In this paper, we have presented FPT algorithms for the KIDNEY EXCHANGE problem with respect to some natural parameters, namely (i) solution size t (the number of patients receiving a kidney), (ii) treewidth+max{ℓp, ℓc} and (iii) the number of vertex types when ℓp ≤ ℓc. For kernelization, we have exhibited a polynomial kernel w.r.t ∆ + t when max{ℓp, ℓc} is O(1). We have complemented this result by refuting existence of a polynomial kernel parameterized ∆ + t + max{ℓp, ℓc} unless NP ⊆ co-NP/poly. We have finally presented an ( 16 9 + ϵ)-approximation algorithm for KIDNEY EXCHANGE in the special case when cycles of length at most 3 are allowed and no path is allowed.

Our work leaves many interesting open questions. One such question is whether KIDNEY EXCHANGE is FPT w.r.t treewidth only. Another such question is whether KIDNEY EXCHANGE is FPT w.r.t number of vertex types (without any assumption on ℓc and ℓp). Another important question is the existence of a polynomial kernel for KIDNEY EXCHANGE parameterized by the solution size alone when the maximum allowed length of paths and cycles are the same. Our hardness proof in Theorem 6 breaks down if we want to allow paths and cycles of the same length. Finally, it is interesting to study whether the running time of our FPT algorithms can be improved further or are they best possible assuming standard complexity-theoretic assumptions like ETH or SETH.