Preferences Single-Peaked on Nice Trees
Authors: Dominik Peters, Edith Elkind
AAAI 2016 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | In this paper, we propose a general framework for answering such questions, and use it to obtain polynomial-time algorithms for identifying nice trees when they exist, for several appealing notions of niceness. Moreover, we show that it has many useful structural properties, which can be exploited to efficiently find trees that have, e.g., the minimum degree, diameter, or number of internal nodes among all trees with respect to which a given profile is single-peaked, or to decide if a given profile is single-peaked on some specific type of tree, such as a caterpillar or a subdivision of a star (see Section 2 for definitions). However, there are limits to what we can accomplish in this way: we show that it is NP-hard to decide whether a given profile is single-peaked on a regular tree. Moreover, given a profile and a tree, it is NP-hard to decide if this profile is single-peaked on this specific tree. |
| Researcher Affiliation | Academia | Dominik Peters and Edith Elkind Department of Computer Science University of Oxford, UK {dominik.peters, edith.elkind}@cs.ox.ac.uk |
| Pseudocode | Yes | Algorithm 1 Build attachment digraph D = (C, A) of V |
| Open Source Code | No | The paper does not provide any statement or link indicating that source code for the methodology is openly available. |
| Open Datasets | No | The paper is theoretical and focuses on algorithms and proofs. It does not use or refer to specific datasets, open or otherwise, for empirical evaluation. |
| Dataset Splits | No | The paper is theoretical and does not involve empirical experiments with dataset splits (training, validation, test). |
| Hardware Specification | No | The paper is theoretical and does not mention any specific hardware used for running experiments. |
| Software Dependencies | No | The paper is theoretical and does not mention specific software dependencies with version numbers required for reproducibility. |
| Experiment Setup | No | The paper is theoretical and does not describe an experimental setup with hyperparameters or system-level training settings. |