Parameterized Complexity of Kidney Exchange Revisited

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 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 PreviousWork 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 (θ)nO(1) , where θ is the number of vertex types in G (two vertices have the same vertex type if they have the same in- and out-neighborhoods 1 ) 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(θ)nO(1) time algorithm for instances of KEP where ℓp ≤ ℓc, and posed as an open problem whether there exists an f(θ)nO(1) -time algorithm for KEP without any assumptions on ℓp, ℓc. Additionally, [Maiti and Dey, 2022] obtain a f(ω + max{ℓp, ℓc})nO(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(ω)nO(1) . Finally, [Maiti and Dey, 2022] considered the number of patients helped (t) as a parameter, and gave an algorithm with running time ∼ 161tnO(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 4tnO(1) (Theorem 2). This improves over the ∼ 161tnO(1) time algorithm of [Maiti and Dey, 2022].
2. KEP admits an algorithm with running time f(θ)nO(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(ω)nO(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 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 ).

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

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 AlgorithmParameterized 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-loops 2 .

Theorem 1 (⋆). KEP admits an algorithm running in time 22O(θ2 log θ) nO(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) ttLO(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,wQ) of G is a directed graph with vertex weights given by wQ : VQ → Z+. Each vertex v ∈ VQ represents a type in G, and the weight wQ(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 graph 3 H = (VH,AH,wH) of Q is an edge-weighted connected graph arc set with wH : AH → Z+ such that VH ⊆ VQ and AH ⊆ AQ.

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

2 Our 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.

3 This is slightly different from the definition in the supplementary material for ease of exposition.

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 wH(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 wQ(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 wQ(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 < wH(e) < 2θ, medium if 2θ ≤ wH(e) ≤ θ3 , and heavy if wH(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 path- or 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 path- or 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

and each arc e ∈ AH, we will have a nonzero variable for the weight wH(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 path- or 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 ′1 SH′ 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 =

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 θ) nO(1) . We formalize this discussion and provide our ILP formulation and algorithm in the supplementary material.

4 Faster FPT AlgorithmParameterized 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 algorithm, 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].

4 The 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

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 +x21x2, the term x1x2 is multilinear, but x21x2 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∗ (2k s(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."

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 12 ) 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) = xi1 xi2 · · · xiℓ , and for each closed walk W2 = j1, j2, . . . , jℓ′ , j1 in D, we define ϕ(W2) = ykxj1 xj2 · · · 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 ∏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 ∑W∈D p(W) = t′ , and such that the degree of D is exactly ℓ. We define the polynomial

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:

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 ∑W∈S (p(W) + 1). This is equal to the degree of the monomial ∏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(ω)nO(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(ω)nO(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 uji be the j th 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:

5 A 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.

• (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 Xie and Xj e , each of size m. We set V (Xe) = Xie ∪ Xj e .

Let xie,ℓ and xje,ℓ denote the ℓth vertex in Xie and Xj e , respectively. For 1 ≤ ℓ < m, the pair (xie,ℓ , xje,ℓ ) 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) (xie,ℓ , xie,ℓ+1 ) and (b) (xje,ℓ , xje,ℓ+1 ) both with weight 1,
• (c) (xie,ℓ , xje,ℓ+1 ) with weight nχV (i)χE(e) + ℓ · nχE(e) ,
• (d) (xje,ℓ , xie,ℓ+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), yi1 , . . . , yin , 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 Xie . 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, yin ) 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. WriteE(vi) = {e1}. We add the following
2. edges to Gkep: (starti, xie1,1 ) and (xj1 e1,me , endi), both with weight 1.
3. |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:
4. (i) (starti, xie1,1 ) and (xj2 e2,me2 , endi), both with weight 1. (ii) (xj1 e1,me1 , xie2,1 ) with weight 1.
5. |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, xie1,1 ) and (xj3 e3,me3 , endi), and (ii) (xj1 e1,me1 , xie2,1 ) and (xj2 e2,me2 , xie3,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).

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 ⋃ 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 (xie,ℓ , xje,ℓ+1 ) or (xje,ℓ , xie,ℓ+1 ), and no other crossing edge in Xe. A cycle intersecting a vertex gadget Yi must follow a path of the form endi, yin , . . . , 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(ω)nO(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(ω)nO(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.

Contribution Statement

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