{"ID":2870947,"CreatedAt":"2026-06-01T04:54:23.091178241Z","UpdatedAt":"2026-06-01T04:54:23.091178241Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2509.11965","arxiv_id":"2509.11965","title":"An ETH-Tight FPT Algorithm for Rejection-Proof Set Packing with Applications to Kidney Exchange","abstract":"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 $\\leq 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 $Σ_2^P$-complete problem that is polynomial in $k$ for all constant values of $d$. We also provide a $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$ 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 $Σ_2^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.","short_abstract":"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 $\\leq d$, covering at least $k$ vertices in total. In...","url_abs":"https://arxiv.org/abs/2509.11965","url_pdf":"https://arxiv.org/pdf/2509.11965v2","authors":"[\"Bart M. P. Jansen\",\"Jeroen S. K. Lamme\",\"Ruben F. A. Verhaegh\"]","published":"2025-09-15T14:18:17Z","proceeding":"cs.DS","tasks":"[\"cs.DS\"]","methods":"[]","has_code":false}