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

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^O (k k) + n^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 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. With a single-exponential algorithm for the setting where c = 1, we show this to be strictly easier under the ETH than when c = 2. In turn, we show that any c 2 yields a problem that is essentially as hard as the original problem with 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.