Research map / Learning theory and algorithms / Sample complexity
The Computational Complexity of Positive Non-Clashing Teaching in Graphs
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Studies the complexity of computing positive non-clashing teaching dimension for balls in graphs, giving NP-hardness for k=2 on split graphs, near-tight ETH bounds, FPT by vertex integrity, and W[1]-hardness for fvs+pathwidth+k.
Problem
Computing the positive non-clashing teaching dimension of a set of concepts, modeled as balls in a graph, in both strict (all balls present) and non-strict settings.
Approach
Reduces positive non-clashing teaching to balls in graphs and derives a near-complete complexity map: a k=2 NP-hardness reduction on split graphs, ETH-tight running-time bounds, an FPT algorithm via vertex integrity using twin-block equivalence and kernelization, and W[1]-hardness for feedback vertex number plus pathwidth.
Key results
- Strict Non-Clash is NP-hard even on split graphs with k=2.
- Non-Clash is FPT parameterized by vertex integrity, with running time 2^{2^{O(p^3)}} · |V(G)|^{O(1)}.
- Non-Clash is W[1]-hard parameterized by fvs(G)+pw(G)+k.
Surprising findings
- Determining whether the positive non-clashing teaching dimension is 1 is trivial in the strict setting, yet NP-hard already at k=2.
Limitations
- Gap between the ETH lower bound and the upper bound of 2^{O(n·d·k·log n)} remains (a logarithmic factor in the exponent).
- Vertex-integrity FPT algorithm has a very large (doubly exponential) dependence on the parameter.
Experimental setup
Baselines: brute-force algorithm
Builds on: non-clashing teaching Chalopin et al. strict non-clash complexity results
Closest papers by meaning
- On a Combinatorial Problem Arising in Machine Teaching (ICML 2024 · similarity 0.86)
- The Parameterized Complexity of Computing the VC-Dimension (NeurIPS 2025 · similarity 0.85)
- Algorithms and Hardness for Active Learning on Graphs (ICML 2025 · similarity 0.85)
- Machine Learning meets Algebraic Combinatorics: A Suite of Datasets Capturing Research-level Conjecturing Ability in Pure Mathematics (ICML 2025 · similarity 0.84)
- Replicability in Learning: Geometric Partitions and KKM-Sperner Lemma (NeurIPS 2024 · similarity 0.84)
- Improved Approximations for Hard Graph Problems using Predictions (ICML 2025 · similarity 0.84)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.