Exact Algorithms and Complexity of Kidney Exchange

1 Introduction

There are two treatment options for kidney disease. One is dialysis, the other is kidney transplantation. The latter is more preferred than the former. A patient may be saved by getting a kidney from a (deceased) donor. Unfortunately, the demand for kidneys far outstrips supply. In general, the average waiting time ranges from 2 to 5 years at most centers and even longer in some geographical regions [Abraham et al., 2007].

Kidney Paired Donation (KPD), also called Kidney Exchange, is put forward to complement the weakness of dead body organ donation via the deceased donor waiting list. KPD is an approach to living donor kidney transplantation where patients with incompatible donors swap kidneys to receive a compatible kidney. Since it was first introduced in [Rapaport, 1986], increasing amount of people have gotten a life-saving kidney with the popularity of KPD, as patients have more opportunities to get saved in this way.

Because better blood type and age matching are correlated with lower lifetime mortality and longer lasting kidney transplants [Segev et al., 2005], many compatible pairs are also participating in swaps to find better matched kidneys. How to swap to save more patients or to get more benefits? This arises the kidney exchange problem.

In kidney exchange, patients and donors participate in cycles and chains. A patient together with his/her donor is regarded as a vertex. In a cycle, a patient in a vertex receives the compatible kidney of the donor in the previous vertex. The number of vertices in a cycle is the length of the cycle. A donor, as soon as the partner patient has received a kidney, can technically exit the program without donating one, as he/she is not legally bound to do so [Roth et al., 2005b; Segev et al., 2005; Mak-Hau, 2017]. In order to avoid this, usually exchanges are carried out simultaneously. This ensures that no donor backs out after his/her paired patient has received a kidney but before he/she donated one of his/her own kidneys [Dickerson et al., 2017]. As each transplant involves two surgeries, there is a limit as to how many exchanges can be performed at once, due to human resource and logistic reasons. Thus, most field kidney exchanges, including UNOS, allow only cycles with small size [Gruessner and Sutherland, 2005].

For chain models, a donor without a paired patient, called the altruistic donor, enters the pool. An altruistic donor is regarded as an altruistic vertex. A sequence of kidney exchanges that begins from an altruistic vertex and terminates at a normal vertex forms a chain. The altruistic donor donates his/her kidney to a patient whose paired donor donates his/her kidney to another patient and so on. The length of a chain is defined to be the number of non-altruistic vertices in the chain, that is, the number of participant patients in it. In real life, chains can be executed non-simultaneously [Anderson et al., 2015]. To see why, consider the situation where a donor backs out of a chain after his/her paired patient received a kidney, but before his/her own donation. Unlike in the case of a broken cycle, no pair in the remaining tail of the planned chain is strictly worse off; that is, no donor was "used up" before his/her paired patient received a kidney. Thus, chains can be much longer than cycles.

We can form kidney exchange problems as graph optimization problems. A pair of patient and donor is regarded as a vertex, an altruistic donor is also regarded as a vertex, and there is a directed arc from a vertex i to a vertex j if the donor in vertex i is compatible to the patient in vertex j. Thus, we get a directed graph called the compatibility graph. Chains in compatibility graph are paths beginning at an altruistic vertex. We want to save patients as more as possible. So it becomes the optimization problem of finding a vertex-disjoint packing of cycles and chains in the compatibility graph to cover maximum number of vertices. This problem is also known as the clearing problem. Note that in compatibility graph, self-loops are allowed, i.e., an arc may begin and end at the same vertex, since some compatible pairs of patient and donor may also want to participate in swaps to find better matched kidneys.

With different constraints, we can get different versions of the problem. Most constraints are about the length of cycles and chains in kidney exchanges. In many previous problem models, the number of participants in a cycle is usually bounded by 3 due to the limitation on human resources in real life [Roth et al., 2005b; Abraham et al., 2007; Biro et al., 2009; Mak-Hau, 2017]. In recent years, with the progress of technology, more and more patients are allowed to participate in cycles and chains. Manlove and O'Malley [2012] demonstrated the benefit of allowing 4-cycle exchanges, when compared with just 2/3-cycle exchanges. A 9-cycle kidney exchange was performed successfully in 2015 at two San Francisco hospitals [Mak-Hau, 2017]. The bounds on the length of cycles and chains may be further increased in the future. We study a general problem with general bounds Lc and Lp on the length of cycles and chains.

(Lc, Lp)-Kidney Exchange ((Lc, Lp)-KEP)

Input: A directed graph G = (V, A) with possible self-loops, an altruistic vertex set B ⊆ V , and two nonnegative integers Lc and Lp.

Output: A set of vertex-disjoint directed cycles and paths covering maximum number of non-altruistic vertices in the graph, where each cycle has length at most Lc and each path begins with an altruistic vertex and has length at most Lp.

In (Lc,Lp)-KEP, we can let Lc and Lp to be 0 to indicate no cycles/chains allowed in the exchange. We also independently consider the version without constraints on the lengths of cycles and chains. In this problem, we want to find out how many patients can be saved "theoretically". We say "theoretically" because we allow the length of cycles and chains at any large.

Free Version of Kidney Exchange (F-KEP)

Input: A directed graph G = (V, A) with possible self-loops and an altruistic vertex set B ⊆ V .

Output: A set of vertex-disjoint directed cycles and paths covering maximum number of non-altruistic vertices in the graph, where each path begins with an altruistic vertex.

1.1 RelatedWork

Since the first introduction of the kidney exchange problem [Rapaport, 1986], many properties and variants have been developed in the following research [Roth et al., 2005b;

2005a; Segev et al., 2005]. Some versions only consider cycles when finding the packing [Constantino et al., 2013; Klimentova et al., 2014; S¨onmez and ¨Unver, 2014], while others consider cycles and chains together [Manlove and O'Malley, 2012; Glorie et al., 2014]. Different restrictions on the length of cycles and chains have also been studied. For example, the problem in [Manlove and O'Malley, 2012] has the same size limitation for cycles and chains. Some may consider looser restrictions on chains [Glorie et al., 2014; Anderson et al., 2015]. Different versions can be regarded as different packing problems in graphs. Some relations between barter exchange and set packing are discussed in [Jia et al., 2017].

Piratical (heuristic) algorithms for real-life data are hot tops and have also been extensively studied. Most of the fast algorithms are based on integer programming [Manlove and O'Malley, 2014; Dickerson et al., 2016; Glorie et al., 2014; Li et al., 2014]. Some other methods can also be found in the literature [Biro et al., 2009; Klimentova et al., 2014; Dickerson et al., 2017]. Some approximation algorithms for different versions are developed by showing the relations to the set packing problem [Krivelevich et al., 2007; Jia et al., 2017]. On the other hand, the NP-hardness of many variants of the kidney exchange problem has been established [Krivelevich et al., 2007].

To make the problems tractable, Dickerson et al. [2017] introduced a way to represent the kidney exchange graph in a compression way by identifying vertices having the same neighborhood properties. In the compatibility graph, vertices are in the same "type" if they have the same in- and outneighborhood. The number of different vertex types may not be very large since they are determined by the blood type, age and some other properties of the patients and donors. Sometimes, we can view it as a constant. Dickerson et al. [2017] show that the kidney exchange problem can be solved in polynomial time when both the length of cycles and chains and the number of different types are bounded by some constants. The concept of "vertex type" is interesting and we can also consider it in this paper.

1.2 Main Contributions

In this paper, we mainly consider exact algorithms for the two fundamental computational problems in kidney exchange: (Lc,Lp)-KEP and F-KEP. In parameterized complexity, we study parameterized problems. An instance of a parameterized problem consists of an instance I of the original (NP-hard) problem and a parameter k. A parameterized problem with parameter k is fixed-parameter tractable (FPT) if and only if it allows an algorithm with running time f(k)poly(|I|), where f(k) is a computable function on k only, and poly(|I|) is a polynomial function on the input size. These kinds of algorithms are called FPT algorithms. Under some reasonable assumptions, some parameterized problems do not allow FPT algorithms, which are W[1]-hard [Downey and Fellows, 2013]. We will consider the kidney exchange problems with the parameter being the number of vertex types. The main contribution of this paper contains two algorithmic results:

1. We show that both of (Lc,Lp)-KEP and F-KEP can

be solved in O(2nn3 ) time. Our algorithms use the techniques of dynamic programming and subset convolution. Note that the trivial search algorithm uses at least nnnO(1) time and most known IP algorithms for kidney exchange problems in the literature have much worse running time bound. Our algorithms use only single exponential running time.

1. We show that F-KEP is FPT by taking the number of vertex types as the parameter, which also implies that F-KEP is polynomially solvable when the numbers of different types of patients and donors are bounded by a constant. The algorithm is based on a decomposition technique and an IP model.

To solve the kidney exchange problem, we mainly work on the compatibility graph solving a cycle/chain packing problem. The compatibility graph G = (V,A) is a directed graph with possible self-loops. We will use n = |V | and m = |A| to denote the numbers of vertices and arcs in the compatibility graph. A set of vertices in G is called an independent set if there is no arc from any vertex to another in the set. A directed complete graph is defined as a graph where each pair of vertices have two arcs from each to other and each vertex also has a self-loop. A single vertex without a self-loop is an independent set and a single vertex with a self-loop is a directed complete graph.

2 Exact Algorithms Based on Subset Convolution

In this section, we design exact algorithms for both (Lc, Lp)- KEP and F-KEP based on dynamic programming and subset convolution. Most previous exact algorithms for variants of the kidney exchange problem are based on IP and the running time of them are not analyzed or take a trivial bound of nnnO(1) at least. We show that (Lc,Lp)-KEP and F-KEP can be solved in 2nnO(1) time by a clever using of subset convolution. In fact, the framework of our algorithms for (Lc,Lp)-KEP and F-KEP are the same, which can even be directly used to design algorithms for more variants of the kidney exchange problem with the same running time bound.

Definition 1. (Packing Unit) Given a graph G = (V,A) with an altruistic vertex set B ⊆ V ,

1. A directed cycle or a directed path starting from an altruistic vertex in G is called a packing unit of F-KEP.
2. A directed cycle of length at most Lc or a directed path starting from an altruistic vertex of length at most Lp is called a packing unit of (Lc, Lp)-KEP.

Sometimes we may simply use the vertex set of a packing unit to denote it. Packing unit is a basic notation used in our algorithms. The definitions of packing units are different for the two problems (Lc, Lp)-KEP and F-KEP. This will be the only difference in our algorithms for the two problems. So we may simply say "packing unit" without specifying for which problems when it is suitable for both cases.

For a packing unit of a cycle, we call it a cycle-packing unit. For a packing unit of a path, we call it a path-packing unit. Note that if a packing unit S is a cycle-packing unit then S contains no altruistic vertex, and if a packing unit S is a path-packing unit then S contains exactly one altruistic vertex. So a vertex subset S can not be both a cycle-packing unit and a path-packing unit.

Our algorithm contains two main steps. In the first step, we use a dynamic programming technique to check each of the 2n vertex subsets whether it is a packing unit or not. The information will be stored in a table D(·) of size 2n . These can be done in O(2nn3 ) time. The algorithm follows the classic dynamic programming algorithm for checking if a graph being a Hamilton graph or not. However, our algorithm needs to check all induced subgraphs of the input graph not only the whole input graph. In the second step, based on D(·), we find out all vertex subsets that can be partitioned into packing units and the one containing maximum number of non-altruistic vertices will be an optimal solution to our problem. We will show that the second step can also be done in O(2nn3 ) time by using subset convolution. Thus, our problems can be solved in O(2nn3 ) time in total.

Step one. The purpose of this step is to find out which vertex subsets are packing units. The information will be store in a table D(·) of size 2n .

For each vertex subset S and two vertices v1, v2 ∈ S, we consider if there is a path in G[S] which starts in v1, visits all vertices in S \ {v1, v2}, and ends in v2. We use a table H(·) to store the information. If it is a yes-case for the triple (S, v1, v2), then H(S, v1, v2) = 1; otherwise H(S, v1, v2) = 0. The size of H is bounded by O(2nn2 ). We use a dynamic programming method to compute the value of H(S, v1, v2) for each S ⊆ V and each vertex pair v1, v2 ∈ S.

For vertex subsets S with size |S| ≤ 2, it is trivial to compute the value H(S, v1, v2). Next, we assume that S is a set containing at least three vertices. For a triple (S, v1, v2), let S∗ be the set of vertices u ∈ S \ {v1, v2} such that there is an arc from u to v2. There is a path P in G[S] which starts in v1, visits all vertices in S \ {v1, v2}, and ends in v2 if and only if there are a vertex u ∈ S∗ and a path P ′ in G[S] which starts in v1, visits all vertices in S \ {v1, v2, u}, and ends in u. So we get the following relation

We compute H(S, v1, v2) in order of increasing cardinality of S by using (1). For each triple (S, v1, v2), the value H(S, v1, v2) can be computed by using at most |S| - 2 basic computations based on the values H(S′ , v′1 , v′2 ) for S′ with cardinality |S′ | = |S| -1. The computation for each element in H(·) takes O(n) basic steps. The size of the table H(·) is bounded by O(2nn2 ). Thus, we can compute all the values in H(·) in O(2nn3 ) time.

Next, we are ready to check if a vertex set S is a packing unit or not based on H(·). We first consider packing units for F-KEP. For (Lc, Lp)-KEP, we only need to add one more constraint on the length of cycles or paths.

We maintain another table D(·) of size 2n . For each vertex subset S ⊆ V , if S is a packing unit then D(S) = 1; otherwise D(S) = 0. The special case S = ∅ will also be used and we let D(∅) = 1. We can compute the values of D(S) for all S ⊆ V in O(2nn) time based on table H(·). It is not hard to see follows.

When S contains no altruistic vertex in B, S can only be a cycle-packing unit if it is a packing unit. So, if S ∩ B = ∅, we compute D(S) by the following way: arbitrarily pick a vertex v ∈ S, let S′ be set of vertices u ∈ S having an arc from u to v, and let

When S contains exactly one altruistic vertex v, S can only be a path-packing unit if it is a packing unit. So, If |S ∩B| = 1, we compute D(S) by the following relation

If |S ∩B| ≥ 2, we simply let D(S) = 0 since it can not be a packing unit.

For (Lc,Lp)-KEP, we only have one more operation to check the size of S. Before executing (2) (resp., (3)), we check weather it holds |S| ≤ Lc (resp., |S| ≤ Lp) or not. If not, we directly let D(S) = 0 without executing (2) or (3).

For each element in D(·), we use at most |S| < n basic computations to calculate it. To compute all the values in D(·), we will use O(2nn) time.

Step two. Equipped with D(·), we will use subset convolution to find out which vertex subsets can be partitioned into disjoint packing units.

Definition 2. (Subset Convolution) Let f be an integer function on subsets of a set V . The subset convolution, or for short the convolution of f, denoted by f ∗ f, is a function assigning to any S ⊆ V an integer as follows

Theorem 1. [Bj¨orklund et al., 2007] Let V be a set of size n and f: 2V → {0, 1} be a function on the subsets of V . If the values of f(S), for all S ⊆ V are given, then the subset convolution f ∗ f can be computed in O(2nn2 ) time.

Subset convolution is a natural tool to solve our problems. An indicator function of a function f , denoted by ̂ f, is defined as: ̂ f(S) = 0 if f(S) = 0 and ̂ f(S) = 1 if f(S) ≥ 1. We list the main steps of our algorithm as follows.

1. f(S) ←D(S) for all S ⊆ V ;
2. For i from 1 to ⌈logn⌉, do g(S) ← (f ∗ f)(S) for all S ⊆ V , and f (S) ← f (S) ∨ ̂ g(S) for all S ⊆ V .
3. The subset S∗ ⊆ V with f(S∗ ) = 1 containing the maximum number of non-altruistic vertices is the solution.

Lemma 1. For any nonempty vertex subset S ⊆ V , if S can be partitioned into at most k disjoint nonempty packing units, then f(S) = 1 after ⌈log k⌉ iterations of Step 2 in the above algorithm.

Proof. We prove the lemma by induction on the number ⌈log k⌉ of iterations of Step 2. Initially f(S′ ) = M(S′ ) for all S′ ⊆ V . Thus, the lemma holds for the first iteration. Assume that the lemma holds after ⌈log k⌉-1 iterations. We prove that the lemma also holds after ⌈log k⌉ iterations.

Since S can be partitioned into at most k disjoint nonempty packing units, we know that there are two disjoint sets S1 and S2 such that S = S1∪S2 and S1 (resp., S2) can be partitioned into at most ⌊ k2 ⌋ (resp., ⌈ k2 ⌉) disjoint nonempty packing units. By the assumption, we know that f(S1) = 1 and f(S2) = 1 after ⌈log(⌈ k2 ⌉)⌉ ≤ ⌈log k⌉-1 iterations. In the next iteration of Step 2, we know that g(S) = (f ∗ f)(S) > 0 by (4). Thus, ̂ g(S) = 1 and then f(S) = 1. It holds for f(S) = 1 after ⌈log k⌉ iterations of Step 2.

Lemma 1 guarantees the correctness of our algorithm. Note that any vertex subset can be partitioned into at most n disjoint nonempty packing units. By Lemma 1, we know that after ⌈logn⌉ iterations of Step 2, the subset S∗ ⊆ V with f(S∗ ) = 1 containing the maximum number of nonaltruistic vertices is our solution. For the running time, we mainly compute ⌈logn⌉ times of subset convolutions. The running time is O(2nn2 ⌈log n⌉).

3 Algorithms for Quotient Models

Dickerson et. al. [2017] introduced a way to class the vertices in a compatibility graph into different types according to some actual meaning and then get a contracted representation of the compatibility graph. Two vertices belong to the same type if and only if they have exactly the same in- and outneighbourhood. In graph theory, a similar notation is known as module. A vertex subset M ⊆ V forms a module of a directed graph if the vertices in M cannot be distinguished by any vertex out of M, i.e., for any vertex x ∈ V \M, if there is an arc from x to a vertex in M (resp., an arc from a vertex in M to x), then there is an arc from x to each vertex in M (resp., an arc from each vertex in M to x). However, the concepts of "type" and "module" are not exactly the same. The concept of "type" has more requirements: any two vertices in the same type M ′ cannot be distinguished by any other vertex, not only vertices out of M ′ . Therefore, for a type M ′ , the induced subgraph M ′ can only be a complete directed graph or an independent set. However, for a moduleM, the induced subgraph M can be of any form. Even the whole vertex set of a graph can be a (trivial) module. For the sake of the presentation, we will call types pure modules.

According to "if and only if" in the definition of type (or pure module), we know that any pure module is maximal (no proper subset is still a pure module) and no two pure modules are intersected. Therefore, the vertex set of a graph can be partitioned into several disjoint pure modules, which is called the pure modular decomposition of a graph. It is known that the pure modular decomposition of a directed graph is unique and it can be found in linear time [McConnell and de Montgolfier, 2005].

Definition 3. (Quotient Graphs) The quotient graph Q = (VQ, AQ, w) of a directed graph G based on a pure modular decomposition is a directed graph with vertex weight w :

V → Z, where each vertex v ∈ VQ represents a pure module in G with the weight w(v) being the number of vertices in the pure module and there is an arc from vertex a to vertex b in AQ if and only if there is an arc from a vertex in the pure module corresponding to a to a vertex in the pure module corresponding to b in G.

Note that the quotient graph may also have self-loops and a pure module of a complete directed clique will have self-loops. Dickerson et. al. [2017] introduced an idea of using quotient graphs to represent big kidney exchange graphs. Furthermore, they showed that (L,L)-KEP can be solved in polynomial time when both L and the number of different pure modules are bounded by a constant by giving an O((n + 1)L·θL )-time algorithm, where θ is the number of different pure modules in the pure modular decomposition of the compatibility graph. However, this algorithm is not FPT with parameter θ since the exponential part of the running time is still related to the input size n. Next, we will give an FPT algorithm for F-KEP with parameter θ.

Our algorithm mainly works on quotient graphs. We first apply the linear-time algorithm [McConnell and de Montgolfier, 2005] to compute the quotient graph Q = (VQ = VI ∪ VC ∪ VB, AQ, w) of the compatibility graph G, where we distinguish three kinds of vertices in VQ: VI is the set of vertices corresponding to the pure modules being independent sets, VC is the set of vertices corresponding to the pure modules being complete directed cliques, and VB is the set of vertices corresponding to altruistic vertices in G.

Given the quotient graph, we first build an integer programming (IP) model to find how many vertices in different pure modules can be included into the solution (the cycle/path packing). Then based on the IP solution, we construct a solution by using a decomposition technique.

3.1 Properties and IPModel

Before giving our IP, we introduce an important property used in the IP. We denote the vertices in VI as {i}p1 , the vertices in VC as {i′ }q1 and the vertices in VB as {i∗ }b1 , where p + q + b = n. Vertex weights w(i), w(i′ ) and w(i∗ ) may be simply written as wi,wi′ and wi∗, respectively.

Definition 4. (Configuration) A configuration of a quotient graph Q = (VQ = VI ∪ VC ∪ VB,AQ,w) of a compatibility graph G is an assignment of nonnegative integers to each vertices and arcs in Q, denoted by A = ({xi}, {xi′}, {xi∗}, {est}). A configuration is feasible if there is a cycle/path packing in G that contains exactly xi (resp., xi′ and xi∗) vertices in the pure module i (resp., i′ and i∗ ), and exactly est arcs from vertices in module s to vertices in module t (include self-loops).

A cycle/path packing can uniquely determines a configuration: the value of each element in the configuration is the number of vertices or edges of this type in the packing. We say that this configuration is corresponding to this cycle/path packing. Note that some configuration may not be corresponding to any cycle/path packing.

Lemma 2. A configuration A = ({xi}, {xi′}, {xi∗}, {est}) is feasible, if and only if it satisfies the following Constraints C1-C6:

Constraint C1 says that the value for each vertex can not excess the weight of the vertex; Constraints C2 and C3 (resp., Constraints C4 and C5) say that for each vertex in VI (resp., VC), its value is equal to the sum of the values of all its inarcs, and its value is an upper bound of the sum of the values of all its out-arcs; Constraint C6 says that for each vertex in VB, its value is equal to the sum of the values of all its outarcs. There are some different between Constraints C2-C3 and Constraints C4-C5, because vertices in pure modules of complete directed cliques have self-loops and can even form cycle containing only one vertex.

For the correctness of Lemma 2, we can easily observe that for any cycle/path packing, the configuration corresponding to it satisfies Constraints C1-C6. For the 'only if' part, we give an algorithm later to construct a cycle/path packing based on a configuration satisfying C1-C6.

Lemma 3. Let A1 = ({xi}, {xi′}, {xi∗}, {est}) be a feasible configuration. The configuration A2 = ({xi}, {wi′}, {xi∗}, {e′st }) is a still feasible configuration, where e′st = est if s ̸= t and e′st = wi′ -xi′ if s = t = i′ .

Proof. Let P1 be the cycle/path packing corresponding toA1. For each i′ , we can add wi′ -xi′ self-loops for vertices in the pure module i′ into P1 to form another cycle/path packing P2. Then P2 is a packing corresponding to A2.

Lemma 4. Let A1 = ({xi}, {xi′}, {xi∗}, {est}) be a feasible configuration such that for any other feasible configuration ({yi}, {yi′}, {yi∗}, {e′st }), it holds

The configuration A2 = ({xi}, {wi′}, {xi∗}, {e′st }) is a feasible configuration corresponding to a cycle/path packing containing the maximum number of non-altruistic vertices in V \ B, where e′st = est if s ̸= t and e′st = wi′ - xi′ if s = t = i′ .

Proof. First, A2 is a feasible configuration by Lemma 3. Second, for any feasible configuration ({yi}, {yi′ }, {yi∗ }, {e′′ st }), it holds that ∑i xi ≥ ∑i yi by the definition of A1 and ∑i wi′ ≥ ∑i yi′ by Lemma 2 and Constraint C1. Therefore, it holds that ∑i xi + ∑i wi′ ≥ ∑i yi + ∑i yi′ and the cycle/path packing corresponding to A2 contains the maximum number of non-altruistic vertices.

Lemma 4 provides a way to find a feasible configuration corresponding to a cycle/path packing containing the maximum number of non-altruistic vertices. We only need to maximize ∑i xi satisfying Constraints C1-C6. Then, we can build an integer programming below, which contains |VQ| + |AQ| integer variables: {xi}, {xi′}, {xi∗} and {est}.

Assume that {{zi}, {zi′}, {zi∗}, {est}} is an optimal solution to the above IP. By Lemma 4, we know that ({zi}, {wi′}, {zi∗}, {e′st }) is a feasible configuration corresponding to an optimal solution to F-KEP.

3.2 The Cycle/Path Decomposition

Next, we show that given an arbitrary feasible configuration, how to construct a cycle/path packing corresponding to it.

Assume that the given feasible configuration is A = ({zi}, {zi′}, {zi∗}, {est}). For each vertex v ∈ V in G, we define In(v) and Out(v) as the sum of the values of all the corresponding pure module's in-arcs and out-arcs in the quotient graph Q. Each of the following two cases is called a packing element in the compatibility graph G under A:

Case 1. a directed cycle C in G (including a self-loop) such that for any vertex or arc in C, the value in A for the corresponding pure module or arc type is positive;

Case 2. a directed path P in G started at an altruistic vertex and ended at a vertex v with In(v) > Out(v) such that for any vertex or arc in P, the value in A for the corresponding pure module or arc type is positive.

Our decomposition algorithm is simple, which iteratively does the follows until all the values in the configuration A become zero: find a packing element and update the configuration A by decreasing the value by 1 for each vertex and arc corresponding to a vertex and arc in the packing element. All the packing elements found by the procedure will form a cycle/path packing.

Lemma 5. Given a feasible configuration and any packing element in the graph. The configuration is still feasible after by decreasing the value by 1 for each vertex and arc corresponding to a vertex and arc in the packing element.

The correctness of this lemma is based on the following observation: for any vertex v in the packing element except the beginning and ending vertices of a path, the update decreases both In(v) and Out(v) by 1, which will not violate any of C1-C6. For a beginning vertex v of a path, it holds that Out(v) > 0 before the update and then it holds that Out(v) ≥ 0 after the update. For an ending vertex v of a path, it holds that In(v) > Out(v) before the update and then it holds that In(v) ≥ Out(v) after the update. Lemma 5 guarantees that after each iteration of the update, the configuration is still feasible. Next, we still need to consider two questions: why proper packing elements always exist during the procedure and how much time needed to find a packing element if it exists. We have the following lemmas.

Lemma 6. When the configuration is feasible, packing elements always exist and one can be found in linear time.

We use a depth-first search (DFS) technique to find a packing element when the configuration satisfies C1-C6. The main procedure is as follows:

If there is a vertex i∗ ∈ VB such that the value xi∗ of it is

greater than 0, we start from i∗ , search by DFS a directed path with all vertices and arcs on it having positive values, until meeting a vertex v with In(v) > Out(v) or a vertex t having been visited. Then we will get a directed path or a directed cycle (started and ended both at t) in Q, which will be corresponding to a packing element of Case 1 or 2 in G;

If the value of any vertex in VB is 0, we start from any vertex with value > 0, search by DFS a directed path with all vertices and arcs on it having positive values, until meeting a vertex having been visited. Then we will get a directed cycle in Q (corresponding to a packing element of Case 1 in G).

Note that when the configuration satisfies C1-C6, only vertices v in VB may hold that In(v) < Out(v) and for any vertex u ∈ VB it holds that In(v) = 0 since there is no arc from a vertex to an altruistic vertex in the graph. When the value of any vertex in VB is 0, it will hold In(v) = Out(v) for any vertex in the graph, because In(v) ≥ Out(v) holds for any vertex v and in global ∑v∈VQ In(v) = ∑v∈VQ Out(v). Therefore, during the above DFS, once the directed path enters a vertex, the vertex should be a vertex with value > 0 and there always has an arc from it to another vertex with positive value. So for the latter case, the DFS can always find a proper cycle.

3.3 Running Time Analysis

The most time-consuming part is the IP. It is known that an IP with x variables can be solved in 2O(x)xx time [Dadush, 2012]. In our IP, the number of variables is the number of vertices and arcs in the quotient graph Q, which is bounded by θ2 (θ = |VQ|). To construct a cycle/apth packing based on a feasible configuration can be done in O(n(n +m)) time, since there are at most n packing elements. In total, the algorithm takes O(2O(θ2 ) θ2θ2 + n(n +m)) time. It is FPT by taking θ as the parameter.

4 Conclusion

This paper contributes to complexity and algorithms with theoretically proved running-time bounds for the kidney exchange problem. We design a uniform single-exponential exact algorithm for the kidney exchange problem with any constraints on the maximum length of the cycles and chains and an FPT algorithm for the kidney exchange problem without length constraints on the cycles and chains. Both results significantly improve previous theoretical bounds. It will be interesting to further study the effectiveness of the two algorithms on realistic instances.

Acknowledgements

The work is supported by the National Natural Science Foundation of China, under grants 61772115 and 61370071.