Rigging Nearly Acyclic Tournaments Is Fixed-Parameter Tractable
Authors: M. Ramanujan, Stefan Szeider
AAAI 2017 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | In this paper we present an algorithm for this problem that exploits structural restrictions on the tournament. More specifically, we establish that the problem is fixed-parameter tractable when parameterized by the size of a smallest feedback arc set of the tournament (interpreting the tournament as an oriented complete graph). This is a natural parameter because most problems on tournaments (including this one) are either trivial or easily solvable on acyclic tournaments, leading to the question what about nearly acyclic tournaments or tournaments with a small feedback arc set? Our result significantly improves upon a recent algorithm by Aziz et al. (2014) whose running time is bounded by an exponential function where the size of a smallest feedback arc set appears in the exponent and the base is the number of players. |
| Researcher Affiliation | Academia | M. S. Ramanujan and Stefan Szeider Algorithms and Complexity Group, TU Wien, Vienna, Austria [ramanujan,sz]@ac.tuwien.ac.at |
| Pseudocode | No | The paper describes an algorithm with four phases in prose but does not provide pseudocode or a formally labeled algorithm block. |
| Open Source Code | No | The paper does not provide any statement or link indicating that source code for the described methodology is open-source or publicly available. |
| Open Datasets | No | This is a theoretical paper focused on algorithmic complexity. It does not involve training models on datasets, and therefore does not mention publicly available training datasets. |
| Dataset Splits | No | This is a theoretical paper focused on algorithmic complexity. It does not involve training or validating models on datasets, and therefore does not mention dataset splits for validation. |
| Hardware Specification | No | This is a theoretical paper. There is no mention of specific hardware used for running experiments, as no empirical experiments are described. |
| Software Dependencies | No | The paper mentions 'ILP-FEASIBILITY' and refers to prior work by Lenstra and Jr., Kannan, and Frank and Tardos, but it does not specify any particular software or library dependencies with version numbers for its own algorithm's implementation. |
| Experiment Setup | No | This is a theoretical paper focused on algorithmic design and complexity. It does not describe an experimental setup with hyperparameters or system-level training settings. |