The Computational Complexity of Positive Non-Clashing Teaching in Graphs
Authors: Robert Ganian, Liana Khazaliya, Fionn Mc Inerney, Mathis Rocton
ICLR 2025 | Venue PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | We study the classical and parameterized complexity of computing the positive non-clashing teaching dimension of a set of concepts, that is, the smallest number of examples per concept required to successfully teach an intelligent learner under the considered, previously established model. For any class of concepts, it is known that this problem can be effortlessly transferred to the setting of balls in a graph G. We establish (1) the NP-hardness of the problem even when restricted to instances with positive non-clashing teaching dimension k = 2 and where all balls in the graph are present, (2) near-tight running time upper and lower bounds for the problem on general graphs, (3) fixed-parameter tractability when parameterized by the vertex integrity of G, and (4) a lower bound excluding fixed-parameter tractability when parameterized by the feedback vertex number and pathwidth of G, even when combined with k. Our results provide a nearly complete understanding of the complexity landscape of computing the positive non-clashing teaching dimension and answer open questions from the literature. |
| Researcher Affiliation | Collaboration | Robert Ganian, Liana Khazaliya & Mathis Rocton Algorithms and Complexity Group, TU Wien, Vienna, Austria EMAIL Fionn Mc Inerney Telef onica Scientific Research, Barcelona, Spain EMAIL |
| Pseudocode | No | The paper describes algorithms (e.g., polynomial-time reduction, kernelization) and computational complexity results, but it does not include any explicitly labeled pseudocode or algorithm blocks. The algorithmic steps are described in prose. |
| Open Source Code | No | The paper does not contain any explicit statement about releasing source code, nor does it provide any links to a code repository. The work is theoretical in nature, focusing on computational complexity. |
| Open Datasets | No | The paper focuses on theoretical computer science, specifically the computational complexity of teaching dimensions in graphs. It does not conduct empirical experiments using real-world datasets. The 'concepts' are defined as 'balls in a graph G', which are abstract mathematical constructs rather than open datasets. |
| Dataset Splits | No | The paper is theoretical and does not involve empirical experiments with datasets. Therefore, there is no mention of dataset splits like training, validation, or test sets. |
| Hardware Specification | No | The paper is a theoretical work on computational complexity and does not describe any experiments that would require specific hardware. Therefore, no hardware specifications are provided. |
| Software Dependencies | No | The paper is theoretical and focuses on computational complexity. It does not describe any implementation or experiments that would require specific software dependencies with version numbers. |
| Experiment Setup | No | The paper focuses on theoretical computer science, specifically computational complexity analysis and algorithm design without empirical validation. Therefore, it does not include any experimental setup details such as hyperparameters, training configurations, or system-level settings. |