Parameterized Complexity of Kidney Exchange Revisited
Authors: Úrsula Hébert-Johnson, Daniel Lokshtanov, Chinmay Sonar, Vaishali Surianarayanan
IJCAI 2024 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | We show that Kidney Exchange is FPT parameterized by the number of vertex types. On the other hand, we show W[1]-hardness with respect to ω. We also design a randomized 4tn O(1)-time algorithm parameterized by t, the number of patients helped, significantly improving upon the previous state of the art, which was 161tn O(1). |
| Researcher Affiliation | Academia | Ursula H ebert-Johnson, Daniel Lokshtanov, Chinmay Sonar and Vaishali Surianarayanan UC Santa Barbara {ursula, daniello, csonar, vaishali}@ucsb.edu |
| Pseudocode | No | The paper describes algorithms conceptually and refers to existing algorithms (e.g., 'reduce the problem to an ILP', 'randomized algorithm'), but does not include any explicit pseudocode blocks or algorithm listings. |
| Open Source Code | No | The paper does not provide any statement or link indicating the availability of open-source code for the described methodology. |
| Open Datasets | No | The paper is theoretical and focuses on algorithm design and complexity analysis; it does not describe experiments using a dataset for training. |
| Dataset Splits | No | The paper is theoretical and does not describe any empirical experiments, thus no dataset validation splits are provided. |
| Hardware Specification | No | The paper is theoretical and does not describe any experiments, therefore no hardware specifications are provided. |
| Software Dependencies | No | The paper is theoretical and does not describe any experiments with specific software dependencies or versions. |
| Experiment Setup | No | The paper is theoretical and does not describe any experiments, therefore no experimental setup details like hyperparameters or training configurations are provided. |