An ETH-Tight FPT Algorithm for Rejection-Proof Set Packing with Applications to Kidney Exchange

Bart M. P. Jansen, Jeroen S. K. Lamme, Ruben F. A. Verhaegh · 2025

Read An ETH-Tight FPT Algorithm for Rejection-Proof Set Packing with Applications to Kidney Exchange by Bart M. P. Jansen, Jeroen S. K. Lamme, Ruben F. A. Verhaegh (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2509-11965.txt.

Introduction

Kidney exchange programs match donors to patients in cycles, but what if one participant group can veto a matching that shortchanges them? Bart M. P. Jansen, with two co-authors, studies that rejection-proof variant in 2025 as a problem in parameterized complexity.

Several agents own the graph's vertices, and an agent rejects a packing of disjoint swap cycles when a different packing would cover more of its own patients. The authors use the sunflower lemma on a set-packing formulation to build a kernel whose size is polynomial in the target for fixed cycle length. From it they get an algorithm whose running time they prove essentially best possible under a standard complexity assumption. A generalized version, where a parameter bounds how far agents may rewrite a packing, drops in difficulty yet resists single-exponential algorithms.

Catalog record

CREATORBart M. P. Jansen, Jeroen S. K. Lamme, Ruben F. A. Verhaegh
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE83 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2509-11965

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

An ETH-Tight FPT Algorithm for Rejection-Proof Set Packing with Applications to Kidney Exchange Bart M. P. Jansen, Jeroen S. K. Lamme, Ruben F. A. Verhaegh Abstract We study the parameterized complexity of a recently introduced multi-agent variant of the Kidney Exchange problem. Given a directed graph G G and integers d d and k k , the standard problem asks whether G G contains a packing of vertex-disjoint cycles, each of length ≤ d \leq d , covering at least k k vertices in total. In the multi-agent setting we consider, the vertex set is partitioned over several agents who reject a cycle packing as solution if it can be modified into an alternative packing that covers more of their own vertices. A cycle packing is called rejection-proof if no agent rejects it and the problem asks whether such a packing exists that covers at least k k vertices. We exploit the sunflower lemma on a set packing formulation of the problem to give a kernel for this Σ 2 P \Sigma_{2}^{P} -complete problem that is polynomial in k k for all constant values of d d . We also provide a 2 𝒪 ⁡ ( k ​ log ⁡ k ) + n 𝒪 ⁡ ( 1 ) 2^{\mathcal{O}(k\log k)}+n^{\mathcal{O}(1)} algorithm based on it and show that this FPT algorithm is asymptotically optimal under the ETH. Further, we generalize the problem by including an additional positive integer c c in the input that naturally captures how much agents can modify a given cycle packing to reject it. For every constant c c , the resulting problem simplifies from being Σ 2 P \Sigma_{2}^{P} -complete to NP-complete. With a single-exponential algorithm for the setting where c = 1 c=1 , we show this to be strictly easier under the ETH than when c = 2 c=2 . In turn, we show that any c ≥ 2 c\geq 2 yields a problem that is essentially as hard as the original problem with c c unbounded. This displays an interesting discrepancy between the classical and parameterized complexity of the problem and gives a good view of what makes it hard. Eindhoven University of Technology, The Netherlands [email protected] https://orcid.org/0000-0001-8204-1268Supported by the Dutch Research Council (NWO) through Gravitation-grant NETWORKS-024.002.003. Eindhoven University of Technology, The Netherlands [email protected] https://orcid.org/0009-0005-8901-2271 Supported by the Dutch Research Council (NWO) through Gravitation-grant NETWORKS-024.002.003. Eindhoven University of Technology, The Netherlands [email protected] https://orcid.org/0009-0008-8568-104X \Crefname claimClaimClaims ccs Theory of computation Parameterized complexity and exact algorithms ccs Applied computing Health informatics ccs Theory of computation Algorithmic game theory ccs Mathematics of computing Combinatorial algorithms keywords Parameterized complexity, Multi-agent kidney exchange, Kernelization, Set packing † † runningtitle: An ETH-Tight FPT Algorithm for Rejection-Proof Set Packing † † runningauthor: B.M.P. Jansen, J.S.K. Lamme, and R.F.A. Verhaegh † † copyright: B.M.P. Jansen, J.S.K. Lamme, and R.F.A. Verhaegh † † editors: John Q. Open and Joan R. Access † † event-title: 42nd Conference on Very Important Topics (CVIT 2016) † † event-shorttitle: CVIT 2016 † † event-acronym: CVIT † † year: 2016 † † event-date: December 24–27, 2016 † † event-location: Little Whinging, United Kingdom † † series-volume: 42 † † articleno: 23 1 Introduction The goal of this paper is to analyze the parameterized complexity of algorithmic problems that arise from a recently introduced multi-party variant of kidney exchange problems. Before describing our results, we first present some relevant context. For patients with severely reduced kidney function, transplantation is often the preferred treatment [ 7 ] . As it is possible to live with only one healthy kidney, live kidney donation is employed to reduce waiting times for sparsely available donor organs. In this setting, a willing donor offers one of their kidneys for transplantation to a patient. The patient and donor must be medically compatible for a successful transplantation. When the patient and donor are not compatible, they can opt to participate in a kidney exchange program (KEP). Such programs aim to link multiple patient-donor pairs so that a donor from one pair is compatible with a patient from another pair. Their goal is to group sets of patient-donor pairs, such that within each group, a cyclic order of compatibility exists. Performing this cycle of transplants means that donors only undergo surgery if their corresponding patient receives a kidney in that exchange. Individual programs each have their own additional restrictions [ 5 ] . It is common to restrict the length of transplantation cycles to some constant d , due to practical considerations which include doing the associated surgeries simultaneously. We study these KEPs from an algorithmic perspective. Given a set of participating patient-donor pairs and the medical compatibilities between them, the algorithmic task becomes to find a combination of transplantation cycles that maximizes the total number of patients receiving a healthy kidney. We can model each patient-donor pair as a vertex and the compatibility of the donor of a pair a to the patient of a pair b as a directed edge from a to b . We call a cycle of length at most d a d -cycle and use this notation to obtain the following algorithmic graph problem that describes KEPs in one of their most basic forms. {tabularx} @ l X Kidney Exchange with d -cycles (KE- d ) Input: A directed graph G and an integer k . Task: Determine whether there is a set \mathcal{C} of pairwise vertex-disjoint d -cycles such that \mathcal{C} covers at least k vertices. This problem has already been studied from the perspective of parameterized algorithms in the literature, with fixed-parameter tractable (FPT) algorithms w.r.t. the input parameter k and the number of neighborhood equivalence classes as examples [ 16 , 20 ] . Multi-agent KEPs Extensions of the standard kidney exchange problem have also been studied. In this work, we consider one such extension which we now motivate and introduce. It is known that the fraction of patients to receive a healthy kidney can increase significantly with an increase in the total number of participating pairs [ 2 ] . This motivates collaborations between multiple programs, from now on referred to as agents. Such collaborations, however, can be hindered by a mismatch between the individual interests of agents, as these need not align with the collective goal of helping as many patients as possible overall. In particular, a socially optimal solution—in which as many patients as possible are treated overall—is not guaranteed to help as many people from each individual agent as that agent could have achieved on their own. This may stop agents from participating in collaborative programs or, when they do participate, move them to withhold information from the collective. Several ways of incorporating fairness into multi-agent KEPs have been studied [ 2 , 3 , 4 , 8 , 9 , 15 , 19 ] . Recently, Blom, Smeulders, and Spieksma [ 6 ] also introduced a framework to capture fairness via a game-theoretical concept of rejections . They translate this into an algorithmic task that asks for a solution that is not rejected by any agent. We study the resulting algorithmic task. To introduce it, we first define the concept of rejections. Recall the original KE- d problem on directed graphs.

Read the complete text