# parameterized_complexity_of_kidney_exchange_revisited__20309c01.pdf

Parameterized Complexity of Kidney Exchange Revisited

Ursula H ebert-Johnson, Daniel Lokshtanov, Chinmay Sonar and Vaishali Surianarayanan UC Santa Barbara {ursula, daniello, csonar, vaishali}@ucsb.edu

As of January 2023, there are more than 90,000 people on the national transplant waiting list in need of a kidney in the United States. These patients often have a friend or family member who is willing to donate, but whose kidney type might not be compatible. To help match these patients to suitable donors, patient-donor compatibility can be modeled as a directed graph. Specifically, in the Kidney Exchange problem, the input is a directed graph G, a subset B of vertices (altruistic donors), and two integers ℓp and ℓc. An altruistic donor is a donor who is not paired with a patient, and the remaining vertices are patient-donor pairs. Whenever a donor is compatible with a patient from a patientdonor pair, we place a directed edge from the donor vertex to the patient-donor pair. Here the donor vertex can be either altruistic or non-altruistic. The goal is to find a collection of vertex-disjoint cycles and paths covering the maximum number of patients such that each cycle has length at most ℓc, and such that each path has length at most ℓp and begins at a vertex in B. The path and cycle lengths are bounded so that the surgeries for a given path or cycle can be performed simultaneously.

Kidney Exchange has received a great deal of attention in recent years. We contribute to this line of work by closing two open problems from IJCAI 18 and IJCAI 22: Is Kidney Exchange FPT when parameterized by (i) the treewidth (ω) of G and (ii) the number of vertex types in G? Two vertices have the same vertex type if they have the same inand out-neighborhoods. We show that Kidney Exchange is FPT parameterized by the number of vertex types. On the other hand, we show W[1]- hardness with respect to ω. We also design a randomized 4tn O(1)-time algorithm parameterized by t, the number of patients helped, significantly improving upon the previous state of the art, which was 161tn O(1).

1 Introduction

Kidney disease is a critical problem that affects tens of thousands of patients in the United States and hundreds of millions across the world [Saran et al., 2020; Kovesdy, 2022]. To avoid a lifetime of dialysis appointments, patients with kidney failure generally join a waiting list to be matched with a compatible donor and receive a transplant. Unfortunately, the demand for kidney donations far exceeds the current number of transplants. In the United States, for example, about 40,000 people join the waiting list for a kidney transplant each year; in comparison, only about 20,000 patients find a match each year. This discrepancy has several implications. Naturally, the number of people on the waiting list is continually increasing. From the year 1995 to the present day, the number of people waiting for a kidney donor has more than doubled, from approximately 42,000 to more than 90,000 [Walsh, 2021]. Because of this, waiting times have become quite long. Currently, the median waiting time for a kidney transplant (from a deceased donor) is 4.05 years in the U.S. [Stewart et al., 2023]. To make matters worse, many patients fail to ever find a match. Thousands of patients are removed from the waiting list each year because they either pass away or simply become too sick to undergo the surgery. Patients in this scenario often have a friend or a family member who is willing to donate a kidney (a paired donor); however, this donor s kidney type might not be compatible with that of the patient. In 2000, the Kidney Paired Donation (KPD) or Kidney Exchange program was introduced [Rapaport, 1986; Roth et al., 2004] to address this issue and increase the number of patients who receive a transplant. KPD is a centrally administered barter-exchange market for kidney donations. A patient with an incompatible donor can participate in the market in the hope of exchanging their donor with a compatible donor from another participating pair. Since its inception, the popularity of KPD has grown, both in terms of the number of participating pairs and in terms of the number of successful transplants. The program now operates in several countries including the United States, the United Kingdom, the Netherlands [Dickerson et al., 2016], and India [Pahwa et al., 2012]. With this program, patients have a higher chance of finding a compatible donor, and some patients can also receive a higher-quality match. For example, matching blood type and age can lead to a longer period of healthy kidney functionality [Segev et al., 2005]. KPD gives

Proceedings of the Thirty-Third International Joint Conference on Artiﬁcial Intelligence (IJCAI-24)

rise to a natural computational problem known as the kidney exchange problem, in which the goal is to maximize the number of patients who receive a transplant. The goal in kidney exchange is to find cycles or chains/paths of compatible patient-donor pairs in order to maximize the number of possible transplants. Therefore, an instance of this problem can be represented as a directed graph: each patient-donor pair is a vertex, and there is a directed edge from a vertex vi to vj if the donor at vi is compatible with the patient at vj. The length of a cycle (resp. path) is defined as the number of edges in the cycle (resp. path). Each patient that belongs to a cycle (resp. path) receives a compatible kidney from the previous vertex on that cycle (resp. path). All transplants from a particular cycle must be done simultaneously as each donor is under no obligation to donate once their paired patient has received a kidney [Roth et al., 2005; Mak-Hau, 2017]. Therefore, to manage the logistics simultaneous transplants, smaller cycles are required in many reallife settings [Abraham et al., 2007; Manlove and O Malley, 2015] including the United Network for Organ Sharing. For a path to be feasible, it must begin with a donor having no paired patient. We refer to such donors as altruistic donors, and we refer to the corresponding vertices as altruistic vertices. We can afford much longer paths compared to the length of cycles [Ashlagi et al., 2012; Dickerson et al., 2016] as in some cases all of the transplants on a path need not be done simultaneously [Anderson et al., 2015]. While sequentially operating on a path, if a donor leaves the program immediately after their paired patient receives a kidney, then in the remainder of the tail no patient is worse off than they were before joining the program. In particular, such patient-donor pairs can re-enter the KPD program. We now define the Kidney Exchange problem formally. The input consists of a directed graph G = (V, A) known as the compatibility graph (whose vertices are altruistic donors and patient-donor pairs), integers ℓp and ℓc, which denote the maximum permissible length for a path or cycle in the solution, respectively, and a subset B V, denoting the altruistic vertices. The remaining set V \ B contains the patient-donor pairs. We have a directed edge (u, v) A if the donor at the vertex u V has a kidney compatible with the patient at v V \ B. The length of a path (resp. cycle) is defined as the number of edges on the path (resp. cycle). We say a path in G is feasible if it starts at an altruistic vertex and has length at least 1 and at most ℓp; a cycle in G is feasible if it has length at most ℓc. We say a path (resp. cycle) covers the non-altruistic vertices (patients) that appear on that path (resp. cycle).

Kidney Exchange Problem (KEP) Input: A directed graph G = (V, A) with no self-loops, an altruistic set B V such that each vertex in B is a source in G, and two nonnegative integers ℓp and ℓc. Goal: Find a set of vertex-disjoint feasible cycles and feasible paths covering the maximum number of nonaltruistic vertices in G.

For the rest of the paper, we denote instances of KEP by (G, B, ℓp, ℓc), and the number of vertices in G by n.

1.1 Previous Work on KEP and Our Contributions Many variants of Kidney Exchange have been studied in recent years, most of which boil down to finding a maximum packing of cycles and paths in a directed graph [Akbarpour et al., 2014; Ashlagi and Roth, 2014; Roth et al., 2005; Segev et al., 2005]. Since this underlying combinatorial problem is NP-hard, many variants of Kidney Exchange are known to be NP-hard even for very restricted cases [Krivelevich et al., 2007; Abraham et al., 2007; Biro et al., 2009]. To cope with this NP-hardness, Kidney Exchange has been studied through the lens of approximation algorithms [Jia et al., 2017; Krivelevich et al., 2007] and parameterized complexity [Xiao and Wang, 2018; Maiti and Dey, 2022]. Our work focuses on the latter, exploring the parameterized complexity of this problem. The Kidney Exchange problem (KEP) as described above was first introduced in [Glorie et al., 2014]. For the special case of KEP where ℓp and ℓc are unrestricted, [Xiao and Wang, 2018] gave an algorithm with running time f(θ)n O(1), where θ is the number of vertex types in G (two vertices have the same vertex type if they have the same inand out-neighborhoods1) and f is a computable function of θ. (Such an algorithm is known as an FPT algorithm parameterized by θ.) Subsequently, [Maiti and Dey, 2022] gave a f(θ)n O(1) time algorithm for instances of KEP where ℓp ℓc, and posed as an open problem whether there exists an f(θ)n O(1)-time algorithm for KEP without any assumptions on ℓp, ℓc. Additionally, [Maiti and Dey, 2022] obtain a f(ω + max{ℓp, ℓc})n O(1)-time algorithm for KEP, where ω is the treewidth of G (a measure of the treelikeness of G), and asked whether KEP can be solved in time f(ω)n O(1). Finally, [Maiti and Dey, 2022] considered the number of patients helped (t) as a parameter, and gave an algorithm with running time 161tn O(1). In this work we make a step forwards towards a more complete understanding of the parameterized complexity of KEP. In particular, we prove the following results: 1. KEP admits a randomized algorithm with running time 4tn O(1) (Theorem 2). This improves over the 161tn O(1) time algorithm of [Maiti and Dey, 2022].

2. KEP admits an algorithm with running time f(θ)n O(1) (Theorem 1). This generalizes the previous algorithms of [Maiti and Dey, 2022; Xiao and Wang, 2018]. 3. Unless FPT = W[1], KEP does not admit an algorithm with running time f(ω)n O(1) (Theorem 3). Our second and third result resolves two open problems of [Maiti and Dey, 2022]. We note that we defer some of our proofs (marked with ) to the supplementary material. Other work on computing exact solutions: Apart from the recent developments in parameterized algorithms, the main approaches in the literature are based on Integer Linear Programming [Roth et al., 2007; Constantino et al., 2013; Mak-Hau, 2017] and the branch and price approach [Barnhart et al., 1998; Plaut et al., 2016]. While these algorithms

1For undirected graphs, the number of types is also referred to as neighborhood diversity in the literature [Lampis, 2012].

Proceedings of the Thirty-Third International Joint Conference on Artiﬁcial Intelligence (IJCAI-24)

are guaranteed to eventually find an optimal solution, no running time guarantees are given. Finally, [Xiao and Wang, 2018] gave a dynamic-programming-based algorithm running in time O(2nn3).

Motivation for studying the parameters θ, t, and ω: Kidney compatibility depends on a few health parameters such as blood type and age. [Dickerson et al., 2017] observed that in real-world Kidney Exchange instances, these take on only few different values. Thus the number of vertex types (θ) in G is typically small. Our other parameters, the number t of patients helped and the treewidth ω of G, are well studied parameters that have improved the understanding of many well-known graph problems. These parameters, being much smaller than n = |V (G)|, help us design algorithms that are faster than the existing exact exponential time algorithms, e.g., the O(2nn3) time algorithm by [Xiao and Wang, 2018]. All three parameters, t, θ and ω, have been studied in the past for KEP and we continue this work.

2 Preliminaries

We represent by N the set of natural numbers including zero. For k N, we denote the set {1, 2, . . . , k} by [k]. Given a graph G and a subset X V (G), we denote the induced subgraph of G on X by G[X]. We say a partition of a multiset X into ℓparts is a collection X1 Xℓof non-overlapping, possibly empty submultisets of X whose union is X. These multisets are non-overlapping in the following sense: for every x X, the multiplicity of x in X is equal to the sum over i of the multiplicity of x in Xi. The treewidth of an undirected graph is a measure of how close the graph is to a tree. We refer the reader to [Cygan et al., 2015] for a complete description of treewidth and tree decompositions. Whenever we mention the treewidth of a directed graph, we refer to the treewidth of the underlying undirected graph. We say two vertices in G have the same vertex type if they are (i) both altruistic or both non-altruistic and (ii) have the same set of in-neighbors and out-neighbors. Let G be an undirected simple graph (graph with no selfloops and multi-edges). A vertex coloring of G using at most c colors is a function from χV : V (G) [c] such that for each edge e = (u, v) E(G), χV (u) = χV (v). For a vertex v in G, we refer to χV (v) as the color of the vertex v. An edge coloring of G using at most c colors is a function from χE : E(G) [c] such that for each pair of distinct edges e1, e2 E(G) having an common end point, χE(e1) = χE(e2). For an edge e in G, we refer to χE(e) as the color of the edge e. We will use greedy coloring and Vizing s theorem [Lewis, 2015] to efficiently obtain a vertex coloring and an edge coloring for our hardness result. Now let H be a directed graph. A walk in H is a sequence of vertices v1, v2, . . . , vk V (H) such that there is a directed edge from vi to vi+1 for all 1 i k 1. A closed or cyclic walk in H is a walk such that v1 = vk. In other words, a walk is a path in which we are allowed to repeat vertices, and a closed walk is a cycle in which we are allowed to repeat vertices. Closed walks with distinct starting points are considered to be distinct: for example, the closed

walk v1, v2, v3, v4, v1 is distinct from v2, v3, v4, v1, v2, assuming the vertices v1, v2, v3, v4 are distinct.

3 FPT Algorithm Parameterized by θ

We fix an instance (G, B, ℓp, ℓc) of KEP. In this section, we outline our FPT algorithm for KEP parameterized by θ, the number of vertex types in G. Vertices of the same type form an independent set since G has no self-loops2.

Theorem 1 ( ). KEP admits an algorithm running in time 22O(θ2 log θ)n O(1), where θ is the number of vertex types in the input graph G.

In our algorithm, we reduce the problem to an ILP with few ( 2O(θ2 log θ)) variables and use an existing [Lenstra Jr, 1983] FPT algorithm for ILPs parameterized by the number of variables.

Proposition 1 ([Lenstra Jr, 1983]). There is an algorithm for computing a feasible as well as an optimal solution of an ILP which is FPT by the number of variables t and runs in time 2O(t)tt LO(1), where L is the total number of bits required to encode the ILP.

For our algorithm, we show that there exists an optimal solution to the problem that can be represented succinctly. We then design an ILP with few variables to find such a succinct representation of an optimal solution. The former is the crux of our result. Due to space constraints, we now give an overview of how to obtain this succinct representation and briefly discuss the ILP. The precise ILP formulation and other details are deferred to the supplementary material. We first show how to represent a solution to KEP in terms of the types in G. We introduce the quotient graph Q to represent G in terms of the types in G. We relate paths (cycles) in the solution to walks (cyclic walks) in Q and extend this relationship to solutions, which are sets of paths and cycles.

Definition 1. The quotient graph Q = (VQ, AQ, w Q) of G is a directed graph with vertex weights given by w Q : VQ Z+. Each vertex v VQ represents a type in G, and the weight w Q(v) is the number of vertices of that type. There is an arc from a vertex u to a vertex v in AQ if and only if there is an arc from a type u vertex to a type v vertex in G. Let BQ VQ be the set of altruistic types.

We can succinctly represent a walk in G by recording how many times it transitions between each pair of vertex types. This is captured by the notion of configuration graphs.

Definition 2. A configuration graph3 H = (VH, AH, w H) of Q is an edge-weighted connected graph arc set with w H : AH Z+ such that VH VQ and AH AQ.

The next definition captures configuration graphs that encode feasible paths and cycles in G.

2Our result can also be extended to allow types that are cliques (for the case with self-loops), but we give an algorithm for the case with only independent sets for ease of exposition. 3This is slightly different from the definition in the supplementary material for ease of exposition.

Proceedings of the Thirty-Third International Joint Conference on Artiﬁcial Intelligence (IJCAI-24)

Definition 3. A configuration graph H is path-feasible (cycle-feasible) if there is a feasible path (cycle) R in G that only uses vertex types from VH, such that for each e = (s, t) AH, R contains exactly w H(e) arcs from vertices of type s to vertices of type t. We say such an R realizes H and denote the configuration realized by R by H(R).

Observe that every path (cycle) R in G realizes the unique configuration H(R), but a configuration can be realized by multiple paths (cycles) covering the same set of vertices in G. Furthermore, a configuration can either be path-feasible or cycle-feasible but not both. One can use Eulerian paths (cycles) to identify path-feasible (cycle feasible) configurations. An Eulerian path (Eulerian cycle) of an edge weighted directed graph G with weight function w : A(G) Z+ on the arc set of G is a walk (cyclic walk) in G that travels through every edge e in G exactly w(e) times. An Eulerian path starts and ends at different vertices in G. The existence of an Eulerian path or Eulerian cycle in G can be verified by checking the connectivity of G and the weighted degrees of each vertex in G. There exists an Eulerian cycle in G if and only if G is connected and for each vertex in G, its weighted in-degree is equal to its weighted out-degree. A slightly modified check can be done for Eulerian paths too.

Lemma 1 ( ). Let H be a configuration graph of Q. H is path-feasible if and only if H contains an Eulerian path of length at most ℓp that starts at an altruistic type and in which each vertex v VH occurs at most w Q(v) times. H is cyclefeasible if and only if H contains an Eulerian cycle of length at most ℓc in which each vertex v VH repeats at most w Q(v) times.

We note that we will have degree constraints in our ILP to check the Eulerian property of configuration graphs, in turn checking the feasibility of paths and cycles by Lemma 1. We are now ready to define how to represent solutions in terms of configuration graphs.

Definition 4. The configuration multiset of a solution S to the instance (G, B, ℓp, ℓc) is the multiset H(S) = {H(R) : R S} of configuration graphs realized by the paths and cycles in S.

Observe that for a solution S, |H(S)| can be much larger than θ, and can even be as large as O(n). So we still need to find a way to express solutions more succinctly. We define an edge e in a configuration graph H to be light if 0 < w H(e) < 2θ, medium if 2θ w H(e) θ3, and heavy if w H(e) > θ3. It would be nice if there always exist an optimal solution S whose configuration multiset H(S) only contained configuration graphs with light and medium edges. There are only few ( f(θ)) such configurations graphs in total and we can fairly easily construct an ILP with few variables to find such a solution. Unfortunately there exist instances for which such an optimal solution does not exist. We now develop tools to handle heavy edges.

Definition 5. A cycle in H is called non-light if it does not contain any light edges. Based on the number of non-light cycles in H, we call H a 0-NL, 1-NL or >1-NL configuration. If H is 1-NL then we denote the unique non-light cycle in H by C(H).

In Definition 5 the number of non-light cycles refers to the number of distinct non-light cycles in H. We do not care whether these cycles overlap or not.

Lemma 2. Every heavy edge in a path-feasible (cyclefeasible) configuration belongs to a non-light cycle.

Proof. Let H be a path-feasible (cycle-feasible) configuration and let e = (u, v) be a heavy edge in AH. Recall that by Definition 2, w(e) > θ3. Suppose e does not belong to a non-light cycle. Then each path from v to u contains a light edge, which by definition has weight less than 2θ. Furthermore, there can be at most θ 2 light edges in H. Thus there is an edge cut S from v to u having weight w(S) < θ3. H contains an Eulerian path (cycle) R because H is path-feasible (cycle-feasible). Then R \ S is a disjoint union of |S| 1 walks. But since w(S) 1 < θ3 and w(e) > θ3, one of these walks uses the edge e at least two times. Thus the walk contains a subwalk from v to u disjoint from S. This contradicts that S cuts u from v.

Lemma 2 immediately implies the following corollary.

Corollary 1. 0-NL configurations have no heavy edges.

A cycle C in Q is a common cycle of two configurations H and H of Q if C is a cycle in both H and H . C is a common non-light cycle in H and H if C is a common cycle of H and H and it is non-light in both H and H . The following Lemma helps bound the number of >1-NL configurations.

Lemma 3 ( ). There exists an optimal solution S to (G, B, ℓp, ℓc) such that for every R1, R2 S, H(R1) and H(R2) do not contain more than one common non-light cycle. Furthermore, there are at most 22θ log(θ) >1-NL configurations in H(S).

Let S be an optimal solution as provided by Lemma 3. We can represent S using H(S ), the configuration multiset of S . However we want to find a way to represent S succinctly so that we can design an ILP with few variables that can find it. Configurations in H(S ) can be partitioned into 0-NL, 1-NL and >1-NL configurations. We first discuss how we handle 0-NL and >1-NL configurations in H(S ). There are at most 2O(θ2 log θ) 0-NL configurations by Definition 2 and Corollary 1, each such configuration H has no heavy edges and has a subgraph of the quotient graph as its underlying graph (VH, AH). Let F0 be the set of all pathor cycle-feasible 0-NL configurations. |F0| 2O(θ2 log θ) and so we can represent all 0-NL configurations in H(S ) succinctly by using a function h0 : F0 Z where h0(H) is the number of occurrences of H in H(S ). In the ILP we construct, we will have a nonnegative variable to compute this count for each H F0. Let F>1 be the set of all pathor cycle-feasible >1-NL configurations. There can be many >1-NL configurations since they have heavy edges, so we cannot use the trick we had for 0-NL configurations. Let O := {GH = (VH, AH) : H H(S ) F>1} be the set of underlying graphs of all >1-NL configurations in H(S ). We can enumerate all of O because there are at most 22θ log(θ) >1-NL configurations in H(S ) by the definition of S . Then for each GH = (VH, AH) O

Proceedings of the Thirty-Third International Joint Conference on Artiﬁcial Intelligence (IJCAI-24)

and each arc e AH, we will have a nonzero variable for the weight w H(e) of e in the ILP. Furthermore, to check feasibility of the configurations, we will add constraints in the ILP to ensure that the conditions of Lemma 1 hold. Let F1 be the set of all pathor cycle-feasible 1-NL configurations and let F 1 be the set of 1-NL configurations with edge weight at most θ3. We now handle 1-NL configurations in H(S ) which can potentially be many. We obtain a succinct representation for these configurations using F 1. Given a nonnegative integer x and a 1-NL configuration H F 1, we define the x-derived configuration of H to be the configuration obtained from H by adding weight x to each edge e on the non-light cycle C(H ). We then show that every 1-NL path(cycle)-feasible configuration H is the x-derived configuration of some H F 1 and some x 0 to prove this we use the Eulerian property of the feasible configuration H (Lemma 1) and the fact that all heavy edges in H lie on the unique non-light cycle C(H) (Lemma 2). Next we partition all the 1-NL configurations in H(S ) into groups H F 1SH based on which configuration H F 1 they can be derived from. If a configuration can be derived from many configurations H F 1, we arbitrarily select one such H F 1 and add H to SH . Finally we represent each group SH in the partition by a triple containing - (i) the configuration H F 1 that the part corresponds to, (ii) |SH | and (iii) the sum t = P

H SH x N: H is x-derived from H x. In the ILP we will add two variables to

find |SH | and t for each group SH . Lastly in the ILP we will also add constraints to ensure the number of vertices of each type used in the solution does not exceed the number of vertices of each type in G. In total, we solve at most 22O(θ log θ) instances of our ILP, each having 2O(θ2 log θ) variables. Using Proposition 1, our

algorithm will run in time 22O(θ2 log θ)n O(1). We formalize this discussion and provide our ILP formulation and algorithm in the supplementary material.

4 Faster FPT Algorithm Parameterized by t

In this section, we describe a randomized FPT algorithm for KEP parameterized by t, the number of patients (i.e., non-altruistic vertices) covered. This algorithm runs in time O (4t), where the O notation suppresses polynomial factors. Since self-loops do not cause any complications in this algorithm, we write this section in a way that allows G to have self-loops. If ℓp t and G contains a path of length t, then we immediately have a solution to our problem. The same is true if ℓc t and G contains a cycle of length ℓ, where t ℓ ℓc. Therefore, we begin by checking whether G contains such a path or cycle. This can be done in randomized time O (4k) [Williams, 2009; Zehavi, 2016].4 For the remainder of our al-

4The algorithm in [Zehavi, 2016] is designed to detect a cycle of length at least t. However, with the following very simple modification, we can use that algorithm to detect a cycle of length ℓ, where t ℓ ℓc: In [Zehavi, 2016], line 6 of Algorithm 1, which says if the path P exists then Accept, should be modified to if the path

gorithm, we update ℓp and ℓc to the values min{ℓp, t 1} and min{ℓc, t 1}, respectively, and thus we can assume ℓp < t and ℓc < t. This first step is similar to [Maiti and Dey, 2022]. In our algorithm, we will work with formal polynomials that have no coefficients. This means we simply think of a polynomial as a string composed of the characters, + , , and the characters representing the variables. If x and y are variables, we abbreviate the string x y as xy, and we abbreviate the string x x x, where there are k copies of x, as xk. We do not plug in values for the variables; each variable is only a symbol. From now on, we will refer to a formal polynomial without coefficients as simply a polynomial, since all of our polynomials will be of that form.

Definition 6. Suppose P(x1, . . . , xn) is a polynomial. A multilinear term in P is a term (monomial) that is a product of distinct variables.

For example, in the polynomial P(x1, x2) = x1x2 +x2 1x2, the term x1x2 is multilinear, but x2 1x2 is not. It is also important to note that in our formal polynomials, addition is commutative, but multiplication is not. For instance, x1 + x2 = x2 + x1, but x1x2 = x2x1. The key idea of our algorithm is as follows: We construct a polynomial Pt that contains a multilinear term if and only if there is a solution covering at least t patients, and then we check whether Pt contains a multilinear term using the following result (Theorem 3.1 in [Williams, 2009]).

Proposition 2. There is a randomized algorithm that takes as input a polynomial P(x1, . . . , xn) of degree at most k, represented by an arithmetic circuit of size s(n) with + gates (of unbounded fan-in), gates (of fan-in two), and no scalar multiplications. This algorithm outputs yes with high probability (at least 1

2) if there is a multilinear term in the sumproduct expansion of P, and always outputs no if there is no multilinear term. The algorithm runs in time O (2ks(n)).

Upon reading the proof of Proposition 2, it becomes apparent that this algorithm only distinguishes between the following two cases:

1. There is no multilinear term in P(x1, . . . , xn),

2. There exists a multilinear term that appears exactly once in P(x1, . . . , xn).

This is usually not an issue because for many problems, the polynomial that one would naturally construct has no repeating terms (for example, in the case of k-path [Williams, 2009]). However, for KEP one must be slightly more careful, since in this case a solution can consist of multiple paths and cycles, and thus there can be distinct solutions that correspond to the same list of vertices, in the same order. Therefore, we will take care to construct a polynomial that has no repeating terms. To apply Proposition 2, we describe a polynomial Pt of degree at most 2t that can be represented by a circuit of size O(t4n3). Once we have constructed such a polynomial, Proposition 2 immediately yields the following theorem. Recall that a solution to KEP is a set of vertexdisjoint feasible paths and feasible cycles.

P exists and is of length at most ℓc k then Accept.

Proceedings of the Thirty-Third International Joint Conference on Artiﬁcial Intelligence (IJCAI-24)

Theorem 2. There is a randomized algorithm that, given an instance of KEP and a positive integer t, outputs yes with high probability (at least 1

2) if there is a solution covering at least t patients, and always outputs no if there is no such solution. This algorithm runs in time O (4t). Fix an instance (G, B, ℓp, ℓc) of KEP. To define Pt, suppose the vertex set of G is {1, . . . , n}, and let x1, . . . , xn be variables corresponding to the vertices of G. We also define t additional variables y1, . . . , yt. We call a walk in G an altruistic walk if its first vertex belongs to B and it has length (number of edges) between 1 and ℓp, inclusive. Suppose D is an ordered collection of (possibly overlapping) altruistic walks and closed walks in G, in which each closed walk has length at most ℓc. We call such a collection D a donation plan if it contains at most t cycles. Note that a donation plan is not required to be feasible the same vertex might be covered multiple times in the same walk or across different walks. In the definition of D, we only consider collections with at most t cycles because we know that if there exists a feasible solution, then there exists a feasible solution with at most t cycles. For each altruistic walk W1 = i1, i2 . . . , iℓin a donation plan D, we define ϕ(W1) = xi1xi2 xiℓ, and for each closed walk W2 = j1, j2, . . . , jℓ , j1 in D, we define ϕ(W2) = ykxj1xj2 xjℓ , where k is such that W2 is the kth closed walk in D. The degree of a donation plan D is the degree of the term Q W D ϕ(W). For a walk W in a donation plan, let p(W) denote the number of patients covered by W, where patients that are covered multiple times along the walk are counted multiple times. Note that this is equal to the edge-length of W. For ℓ, t 1, let Πt ℓbe the collection of all donation plans D such that P W D p(W) = t , and such that the degree of D is exactly ℓ. We define the polynomial

Pt(x1, . . . , xn, y1, . . . , yt) =

In the product over W D, we multiply the terms ϕ(W) in order, according to the ordering of the walks in D. First, to ensure that we can apply Proposition 2, we observe that distinct donation plans give rise to distinct terms in Pt: Observation 1 ( ). If Q W D1 ϕ(W) = Q W D2 ϕ(W) for donation plans D1, D2, then D1 = D2. As mentioned above, proofs of results marked with a star can be found in the supplementary material. Now, we need to show that Pt contains a multilinear term if and only if there is a solution covering at least t patients: Lemma 4 ( ). There is a solution to (G, B, ℓp, ℓc) covering at least t patients if and only if Pt contains a multilinear term. The following lemma (Lemma 5) is a key step in the proof of Lemma 4. For the statement of Lemma 5, we need one more definition: Let S be a solution to the given instance of KEP. The degree of S is defined as P W S(p(W) + 1). This is equal to the degree of the monomial Q W D ϕ(W), where D is any ordering of S. Lemma 5 ( ). If there exists a solution to the instance (G, B, ℓp, ℓc) that covers at least t patients, then there exists

a solution S with the following properties: the number of patients covered by S is at least t and at most 2t, and the degree of S is at most 2t.

Finally, to properly apply Proposition 2, we must be able to build a circuit that computes Pt. This can be done in a similar way to the algorithm for k-path [Williams, 2009]. The details can be found in the supplementary material.

5 W[1]-Hardness of KEP Parameterized by ω

In this section, we will show that KEP does not admit an algorithm with running time f(ω)n O(1), where ω is the treewidth of the compatibility graph, unless FPT = W[1]. We prove this by showing that KEP is W[1]-hard parameterized by ω.

Theorem 3. KEP is W[1]-hard. Unless FPT = W[1], KEP does not admit an algorithm with running time f(ω)n O(1).

To prove Theorem 3, we give a reduction from the following W[1]-hard variant of the Multicolored Clique problem. 5

Dense k-Multicolored Clique Parameter: k Input: A positive integer k > 3, a k-partite graph G = (V = V1 V2 Vk, E), and a graph Gaux = (Vaux, Eaux) constructed from G with the following properties: (i) In G, |Vi| = n for all i [k], where n N, (ii) for all i, G[Vi Vj] is not a complete bipartite graph for at most three j = i, (iii) Vaux = {v1, . . . , vk}, where vi for i [k] corresponds to the vertex set Vi in G, (iv) for i, j [k] with i = j, (vi, vj) Eaux if and only if G[Vi Vj] is not a complete bipartite graph, and (v) Gaux is triangle free. Question: Does there exist a k-clique S V with |S Vi| = 1 for all i?

Let (G = (V1 V2 Vk, E), k) be an instance of Dense k-Multicolored Clique. We refer to each partition Vi of G as a color class of G. Let uj i be the jth vertex in Vi for 1 j n and 1 i k. We choose an arbitrary ordering of the vertices and edges of G, Gaux. We observe that the maximum degree of a vertex in Gaux is 3; therefore, using Vizing s Theorem [Lewis, 2015] we can obtain a proper vertex coloring χV : V (Gaux) {1, 2, 3, 4} and a proper edge coloring χE : E(Gaux) {5, 10, 15, 20} in polynomial time. For a vertex vi Vaux, we denote the set of edges incident to vi in Gaux by E(vi). We now give the construction of a (0, n25)-KEP instance (G, , 0, n25), where G = (V, A), using G, Gaux, χV , and χE. We will first construct an edge-weighted directed graph Gkep. We will then construct G from Gkep by replacing every edge e with weight we from u to v in Gkep by a new path from u to v having we 1 internal vertices. Our construction has the following two types of gadgets:

5A simple reduction from the W[1]-hard problem Partitioned Subgraph Isomorphism (PSI) [Lokshtanov et al., 2020, Proposition 3.1] [Marx, 2007, Corollary 6.3] shows W[1]-hardness for our variant of MCC. See the supplementary material for further details. Also, we define MCC as above to get a cleaner reduction.

Proceedings of the Thirty-Third International Joint Conference on Artiﬁcial Intelligence (IJCAI-24)

(i) Edge gadgets (Xe): For each edge e Eaux, we add an edge gadget Xe to Gkep. Vertices of Xe: Suppose e = (vi, vj). Let m = |E(G[Vi, Vj])| + 1. We construct two ordered sets of vertices Xi e and Xj e, each of size m. We set V (Xe) = Xi e Xj e. Let xi e,ℓand xj e,ℓdenote the ℓth vertex in Xi e and Xj e, respectively. For 1 ℓ< m, the pair (xi e,ℓ, xj e,ℓ) corresponds to the ℓth edge in E(G[Vi, Vj]). We now define two mappings f i e : [m 1] Vi and f j e : [m 1] Vj. If (ui Vi, uj Vj) is the ℓth edge in E(G[Vi, Vj]), then f i e(ℓ) := ui and f j e(ℓ) := uj. These mappings will later be used to assign weights to the edges of Gkep. Edges of Xe: For each 1 ℓ< m, we add the following four types of directed edges: (a) xi e,ℓ, xi e,ℓ+1 and (b) xj e,ℓ, xj e,ℓ+1 both with weight 1, (c) xi e,ℓ, xj e,ℓ+1 with weight nχV (i)χE(e) + ℓ nχE(e), (d) xj e,ℓ, xi e,ℓ+1 with weight nχV (j)χE(e) + ℓ nχE(e). We call the edges of type (c) and (d) crossing edges.

(ii) Vertex gadgets (Yi): For each vertex vi Vaux, we add a vertex gadget Yi to Gkep. V (Yi): Let V (Yi) = {starti(si), yi 1, . . . , yi n, endi(ei)}, where each yi ℓfor 1 ℓ n corresponds to the ℓth vertex uℓ Vi. Note that |V (Yi)| = n + 2. Edges of Yi: Recall that E(vi) Eaux is the set of edges incident to vi. We add the following edges to Yi: (a) yi ℓ, starti with weight n25 sumℓ for each 1 ℓ n, where sumℓ= Σe E(vi)me + (nχV (vi) + ℓ)(Σe E(vi)nχE(e))+n ℓ+2, and where me is the number of vertices in set Xi e. Recall that me is one plus the number of edges between the color classes Vi, Vj. (b) yi ℓ, yi ℓ 1 with weight 1 for each 2 ℓ n. (c) endi, yi n with weight 1.

Linking the edge and vertex gadgets: We now link our gadgets together to complete the construction of Gkep. For each vi Vaux, we consider the following three cases according to the cardinality of E(vi): 1. |E(vi)| = 1. Write E(vi) = {e1}. We add the following edges to Gkep: (starti, xi e1,1) and (xj1 e1,me, endi), both with weight 1.

2. |E(vi)| = 2. Write E(vi) = {e1, e2}, and let e1 < e2 be the ordering of the edges. We add the following edges to Gkep: (i) (starti, xi e1,1) and (xj2 e2,me2 , endi), both with weight 1. (ii) (xj1 e1,me1 , xi e2,1) with weight 1.

3. |E(vi)| = 3. Write E(vi) = {e1, e2, e3}, and suppose e1 < e2 < e3 is the ordering of those edges. We add the following edges to Gkep: (i) (starti, xi e1,1) and (xj3 e3,me3 , endi), and (ii) (xj1 e1,me1 , xi e2,1) and (xj2 e2,me2 , xi e3,1), all with weight 1.

Since Gaux has k vertices each of degree at most 3, Gkep has k vertex gadgets and at most 3k/2 edge gadgets. Recall

that G is constructed by replacing each edge in Gkep with a path. Since replacing an edge with a path does not increase the treewidth of the graph, to show that the treewidth of G is O(k), it suffices to show that the treewidth of Gkep is O(k).

Observation 2 ( ). The treewidth of Gkep is O(k).

There exists a k-MCC in G if and only if there is a solution to the constructed (0, n25)-KEP instance (G, , 0, n25) which covers at least kn25 patients. Due to limited space, we defer the formal proof of equivalence to the supplementary material. We will now describe the structure of cycles in the solution and give a high-level idea of our proof. We say a cycle intersects an edge gadget Xe (resp. a vertex gadget Yi) if it has nonempty intersection with V (Xe) (resp. V (Yi)). Consider Xe, where e = (vi, vj) Eaux. Suppose (ui, uj) E(G[Vi S Vj]), where ui Vi and uj Vj is the ℓth edge in Xe. We say a cycle intersecting Xe selects the edge (ui, uj) if it contains one of the two crossing edges (xi e,ℓ, xj e,ℓ+1) or (xj e,ℓ, xi e,ℓ+1), and no other crossing edge in Xe. A cycle intersecting a vertex gadget Yi must follow a path of the form endi, yi n, . . . , yi ℓ, starti for some n ℓ 1 since the only way to enter and exit a vertex gadget is through endi and starti, respectively. We say such a cycle selects the vertex uℓ(corresponding to yℓ), where uℓ Vi. In our proof, we show that (i) each cycle in the solution for (G, , 0, n25) intersects one vertex gadget and at most three edge gadgets, (ii) if the vertex gadget corresponds to vi Vaux, then the three edge gadgets correspond to the edges incident to vi in Gaux, and (iii) all of the edges selected across the three edge gadgets are incident to the vertex selected in the vertex gadget. Finally, we show that the k vertices selected by the k cycles in the solution form a clique in G.

6 Discussion and Open Problems

In this work, we considered KEP, a natural problem of matching kidney patients to donors. We made significant progress in understanding its parameterized complexity. Our randomized algorithm from Theorem 2 can be derandomized to run in time 14.34t using a deterministic version of Proposition 2 [Fomin et al., 2014, Theorem 5.1]. Furthermore, we believe our algorithms can be used for designing local-searchstyle heuristics. For instance, algebraic algorithms for MOTIF FINDING led to a highly parallelized implementation for this problem on GPUs [Kaski et al., 2018]. In Section 5, we show that KEP is W[1]-hard parameterized by ω. Lampis [Lampis, 2014] introduced a technique to design approximation schemes running in f(ω)n O(1) time for problems that are W[1]-hard with respect to ω. This technique uses tools from approximation algorithms over tree decompositions. We remark that a direct application of this technique would yield a bicriteria approximation scheme for t and max(ℓp, ℓc) for KEP running in time f(ω)n O(1). Approximating just the solution size t within a similar running time would also be interesting. Another nice open problem that stems from our work would be to ask whether there exists a single-exponential FPT algorithm parameterized by the number of vertex types.

Proceedings of the Thirty-Third International Joint Conference on Artiﬁcial Intelligence (IJCAI-24)

Contribution Statement

All authors contributed equally to this work. Their names are ordered alphabetically by last name.

References [Abraham et al., 2007] David J Abraham, Avrim Blum, and Tuomas Sandholm. Clearing algorithms for barter exchange markets: Enabling nationwide kidney exchanges. In Proceedings of the 8th ACM conference on Electronic commerce, pages 295 304, 2007. [Akbarpour et al., 2014] Mohammad Akbarpour, Shengwu Li, and Shayan Oveis Gharan. Dynamic matching market design. ar Xiv preprint ar Xiv:1402.3643, 2014. [Anderson et al., 2015] Ross Anderson, Itai Ashlagi, David Gamarnik, and Alvin E Roth. Finding long chains in kidney exchange using the traveling salesman problem. Proceedings of the National Academy of Sciences, 112(3):663 668, 2015. [Ashlagi and Roth, 2014] Itai Ashlagi and Alvin E Roth. Free riding and participation in large scale, multi-hospital kidney exchange. Theoretical Economics, 9(3):817 863, 2014. [Ashlagi et al., 2012] Itai Ashlagi, David Gamarnik, Michael A Rees, and Alvin E Roth. The need for (long) chains in kidney exchange. Technical report, National Bureau of Economic Research, 2012. [Barnhart et al., 1998] Cynthia Barnhart, Ellis L Johnson, George L Nemhauser, Martin WP Savelsbergh, and Pamela H Vance. Branch-and-price: Column generation for solving huge integer programs. Operations research, 46(3):316 329, 1998. [Biro et al., 2009] P eter Biro, David F Manlove, and Romeo Rizzi. Maximum weight cycle packing in directed graphs, with application to kidney exchange programs. Discrete Mathematics, Algorithms and Applications, 1(04):499 517, 2009. [Constantino et al., 2013] Miguel Constantino, Xenia Klimentova, Ana Viana, and Abdur Rais. New insights on integer-programming models for the kidney exchange problem. European Journal of Operational Research, 231(1):57 68, 2013. [Cygan et al., 2015] Marek Cygan, Fedor V Fomin, Łukasz Kowalik, Daniel Lokshtanov, D aniel Marx, Marcin Pilipczuk, Michał Pilipczuk, and Saket Saurabh. Parameterized algorithms, volume 5. Springer, 2015. [Dickerson et al., 2016] John P Dickerson, David F Manlove, Benjamin Plaut, Tuomas Sandholm, and James Trimble. Position-indexed formulations for kidney exchange. In Proceedings of the 2016 ACM Conference on Economics and Computation, pages 25 42, 2016. [Dickerson et al., 2017] John P. Dickerson, Aleksandr M. Kazachkov, Ariel D. Procaccia, and Tuomas Sandholm. Small representations of big kidney exchange graphs. In The Workshops of the The Thirty-First AAAI Conference

on Artificial Intelligence, Saturday, February 4-9, 2017, San Francisco, California, USA, volume WS-17 of AAAI Technical Report. AAAI Press, 2017.

[Fomin et al., 2014] Fedor V. Fomin, Daniel Lokshtanov, Fahad Panolan, and Saket Saurabh. Representative sets of product families, 2014.

[Glorie et al., 2014] Kristiaan M Glorie, J Joris van de Klundert, and Albert PM Wagelmans. Kidney exchange with long chains: An efficient pricing algorithm for clearing barter exchanges with branch-and-price. Manufacturing & Service Operations Management, 16(4):498 512, 2014.

[Jia et al., 2017] Zhipeng Jia, Pingzhong Tang, Ruosong Wang, and Hanrui Zhang. Efficient near-optimal algorithms for barter exchange. In Proceedings of the 16th Conference on Autonomous Agents and Multi Agent Systems, pages 362 370, 2017.

[Kaski et al., 2018] Petteri Kaski, Juho Lauri, and Suhas Thejaswi. Engineering motif search for large motifs. In Gianlorenzo D Angelo, editor, 17th International Symposium on Experimental Algorithms, SEA 2018, June 27-29, 2018, L Aquila, Italy, volume 103 of LIPIcs, pages 28:1 28:19. Schloss Dagstuhl - Leibniz-Zentrum f ur Informatik, 2018.

[Kovesdy, 2022] Csaba P Kovesdy. Epidemiology of chronic kidney disease: An update 2022. Kidney International Supplements, 12(1):7 11, 2022.

[Krivelevich et al., 2007] Michael Krivelevich, Zeev Nutov, Mohammad R Salavatipour, Jacques Verstraete, and Raphael Yuster. Approximation algorithms and hardness results for cycle packing problems. ACM Transactions on Algorithms (TALG), 3(4):48 es, 2007.

[Lampis, 2012] Michael Lampis. Algorithmic metatheorems for restrictions of treewidth. Algorithmica, 64(1):19 37, 2012.

[Lampis, 2014] Michael Lampis. Parameterized approximation schemes using graph widths. In Automata, Languages, and Programming: 41st International Colloquium, ICALP 2014, Copenhagen, Denmark, July 8-11, 2014, Proceedings, Part I 41, pages 775 786. Springer, 2014.

[Lenstra Jr, 1983] Hendrik W Lenstra Jr. Integer programming with a fixed number of variables. Mathematics of operations research, 8(4):538 548, 1983.

[Lewis, 2015] Rhyd Lewis. A guide to graph colouring, volume 7. Springer, 2015.

[Lokshtanov et al., 2020] Daniel Lokshtanov, MS Ramanujan, Saket Saurab, and Meirav Zehavi. Parameterized complexity and approximability of directed odd cycle transversal. In Proceedings of the Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 2181 2200. SIAM, 2020.

[Maiti and Dey, 2022] Arnab Maiti and Palash Dey. Parameterized algorithms for kidney exchange. In Lud De

Proceedings of the Thirty-Third International Joint Conference on Artiﬁcial Intelligence (IJCAI-24)

Raedt, editor, Proceedings of the Thirty-First International Joint Conference on Artificial Intelligence, IJCAI22, pages 405 411. International Joint Conferences on Artificial Intelligence Organization, 7 2022. Main Track. [Mak-Hau, 2017] Vicky Mak-Hau. On the kidney exchange problem: cardinality constrained cycle and chain problems on directed graphs: a survey of integer programming approaches. Journal of combinatorial optimization, 33(1):35 59, 2017. [Manlove and O Malley, 2015] David F Manlove and Gregg O Malley. Paired and altruistic kidney donation in the uk: Algorithms and experimentation. Journal of Experimental Algorithmics (JEA), 19:1 21, 2015. [Marx, 2007] D aniel Marx. Can you beat treewidth? In 48th Annual IEEE Symposium on Foundations of Computer Science (FOCS 07), pages 169 179. IEEE, 2007. [Pahwa et al., 2012] Mrinal Pahwa, Yusuf Saifee, Vipin Tyagi, Sudhir Chadha, and Harsh Jauhari. Paired exchange kidney donation in india: A five-year single-center experience. International urology and nephrology, 44(4):1101 1105, 2012. [Plaut et al., 2016] Benjamin Plaut, John P Dickerson, and Tuomas Sandholm. Fast optimal clearing of capped-chain barter exchanges. In Thirtieth AAAI Conference on Artificial Intelligence, 2016. [Rapaport, 1986] Felix T Rapaport. The case for a living emotionally related international kidney donor exchange registry. In Transplantation proceedings, volume 18, pages 5 9, 1986. [Roth et al., 2004] Alvin E Roth, Tayfun S onmez, and M Utku Unver. Kidney exchange. The Quarterly journal of economics, 119(2):457 488, 2004. [Roth et al., 2005] Alvin E Roth, Tayfun S onmez, and M Utku Unver. Pairwise kidney exchange. Journal of Economic theory, 125(2):151 188, 2005. [Roth et al., 2007] Alvin E Roth, Tayfun S onmez, and M Utku Unver. Efficient kidney exchange: Coincidence of wants in markets with compatibility-based preferences. American Economic Review, 97(3):828 851, 2007. [Saran et al., 2020] Rajiv Saran, Bruce Robinson, Kevin C Abbott, Jennifer Bragg-Gresham, Xiaoying Chen, Debbie Gipson, Haoyu Gu, Richard A Hirth, David Hutton, Yan Jin, et al. US renal data system 2019 annual data report: Epidemiology of kidney disease in the United States. American Journal of Kidney Diseases, 75(1):A6 A7, 2020. [Segev et al., 2005] Dorry L Segev, Sommer E Gentry, Daniel S Warren, Brigitte Reeb, and Robert A Montgomery. Kidney paired donation and optimizing the use of live donor organs. Jama, 293(15):1883 1890, 2005. [Stewart et al., 2023] Darren Stewart, Tatenda Mupfudze, and David Klassen. Does anybody really know what (the kidney median waiting) time is? American Journal of Transplantation, 23(2):223 231, 2023.

[Walsh, 2021] Dylan Walsh. A beautiful application: Using economics to make kidney exchanges more efficient and fair. Stanford Graduate School of Business, 2021. [Williams, 2009] Ryan Williams. Finding paths of length k in O (2k) time. Information Processing Letters, 109(6):315 318, 2009. [Xiao and Wang, 2018] Mingyu Xiao and Xuanbei Wang. Exact algorithms and complexity of kidney exchange. In IJCAI, pages 555 561, 2018. [Zehavi, 2016] Meirav Zehavi. A randomized algorithm for long directed cycle. Information Processing Letters, 116(6):419 422, 2016.

Proceedings of the Thirty-Third International Joint Conference on Artiﬁcial Intelligence (IJCAI-24)