2026-08-17T08:55:38Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:25141 2026-02-11T14:14:08Z ddc:004 open_access

An ETH-Tight FPT Algorithm for Rejection-Proof Set Packing with Applications to Kidney Exchange Jansen, Bart M. P. Lamme, Jeroen S. K. Verhaegh, Ruben F. A. Parameterized complexity Multi-agent kidney exchange Kernelization Set packing We study the parameterized complexity of a recently introduced multi-agent variant of the Kidney Exchange problem. Given a directed graph G and integers d and k, the standard problem asks whether G contains a packing of vertex-disjoint cycles, each of length ≤ d, covering at least 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 vertices. We exploit the sunflower lemma on a set packing formulation of the problem to give a kernel for this Σ₂^P-complete problem that is polynomial in k for all constant values of d. We also provide a 2^𝒪(k log k) + n^𝒪(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 in the input that naturally captures how much agents can modify a given cycle packing to reject it. For every constant c, the resulting problem simplifies from being Σ₂^P-complete to NP-complete. The super-exponential lower bound already holds for c = 2, though. We present an ad-hoc single-exponential algorithm for c = 1. These results reveal an interesting discrepancy between the classical and parameterized complexity of the problem and give a good view of what makes it hard. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Bart M. P. Jansen and Jeroen S. K. Lamme and Ruben F. A. Verhaegh 2025 Is Part Of LIPIcs, Volume 358, 20th International Symposium on Parameterized and Exact Computation (IPEC 2025) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.IPEC.2025.9 urn:nbn:de:0030-drops-251414 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.IPEC.2025.9 eng https://creativecommons.org/licenses/by/4.0/legalcode