# Non-Clashing Teaching Maps for Balls in Graphs

arXiv: https://arxiv.org/abs/2309.02876 · HTML: https://mlsanity.com/paper/2309.02876/

## Key facts

- Cited by 6 papers in the map (data through 14 Oct 2026).
- Builds on 17 of its 68 references that are in the map.
- First posted on arXiv 6 Sep 2023.

## Builds on (most cited first, 17 of 17)

- [An Overview of Machine Teaching](https://mlsanity.com/paper/1801.05927/) (2018)
- [Learning Mixtures of Linear Regressions with Nearly Optimal Complexity](https://mlsanity.com/paper/1802.07895/) (2018)
- [Machine Teaching for Inverse Reinforcement Learning: Algorithms and Applications](https://mlsanity.com/paper/1805.07687/) (2018)
- [Training Set Debugging Using Trusted Items](https://mlsanity.com/paper/1801.08019/) (2018)
- [Understanding the Role of Adaptivity in Machine Teaching: The Case of Version Space Learners](https://mlsanity.com/paper/1802.05190/) (2018)
- [Unlabeled sample compression schemes and corner peelings for ample and maximum classes](https://mlsanity.com/paper/1812.02099/) (2018)
- [Preference-Based Batch and Sequential Teaching: Towards a Unified View of Models](https://mlsanity.com/paper/1910.10944/) (2019)
- [Labeled compression schemes for extremal classes](https://mlsanity.com/paper/1506.00165/) (2015)
- [Preference-based Teaching](https://mlsanity.com/paper/1702.02047/) (2017)
- [Sample compression schemes for balls in graphs](https://mlsanity.com/paper/2206.13254/) (2022)
- [Optimal Collusion-Free Teaching](https://mlsanity.com/paper/1903.04012/) (2019)
- [Labeled sample compression schemes for complexes of oriented matroids](https://mlsanity.com/paper/2110.15168/) (2021)
- [Quadratic Upper Bound for Recursive Teaching Dimension of Finite VC Classes](https://mlsanity.com/paper/1702.05677/) (2017)
- [Unlabeled Compression Schemes Exceeding the VC-dimension](https://mlsanity.com/paper/1811.12471/) (2018)
- [A Parameterized Theory of PAC Learning](https://mlsanity.com/paper/2304.14058/) (2023)
- [Problems in NP can Admit Double-Exponential Lower Bounds when Parameterized by Treewidth or Vertex Cover](https://mlsanity.com/paper/2307.08149/) (2023)
- [Parameterized Max Min Feedback Vertex Set](https://mlsanity.com/paper/2302.09604/) (2023)

## Built on by (most cited first, 6 of 6)

- [The Computational Complexity of Positive Non-Clashing Teaching in Graphs](https://mlsanity.com/paper/2503.07665/) (2025)
- [The Parameterized Complexity of Computing the VC-Dimension](https://mlsanity.com/paper/2510.17451/) (2025)
- [Efficient Algorithms for Learning and Compressing Monophonic Halfspaces in Graphs](https://mlsanity.com/paper/2506.23186/) (2025)
- [Non-Clashing Teaching in Graphs: Algorithms, Complexity, and Bounds](https://mlsanity.com/paper/2602.00657/) (2026)
- [A Structural Complexity Analysis of Hierarchical Task Network Planning](https://mlsanity.com/paper/2401.14174/) (2024)
- [On Collusion-Free Teaching in Planar Graphs](https://mlsanity.com/paper/2610.18714/) (2026)

## Abstract (arXiv)

Recently, Kirkpatrick et al. [ALT 2019] and Fallat et al. [JMLR 2023] introduced non-clashing teaching and showed it is the most efficient machine teaching model satisfying the Goldman-Mathias collusion-avoidance criterion. A teaching map T for a concept class C assigns a (teaching) set T(C) of examples to each concept C ∈ C. A teaching map is non-clashing if no pair of concepts are consistent with the union of their teaching sets. The size of a non-clashing teaching map (NCTM) T is the maximum size of a teaching set T(C), C ∈ C. The non-clashing teaching dimension NCTD(C) of C is the minimum size of an NCTM for C. NCTM^+ and NCTD^+(C) are defined analogously, except the teacher may only use positive examples. We study NCTMs and NCTM^+s for the concept class B(G) consisting of all balls of a graph G. We show that the associated decision problem B-NCTD^+ for NCTD^+ is NP-complete in split, co-bipartite, and bipartite graphs. Surprisingly, we even prove that, unless the ETH fails, B-NCTD^+ does not admit an algorithm running in time 2^2o(vc)· nO(1), nor a kernelization algorithm outputting a kernel with 2o(vc) vertices, where vc is the vertex cover number of G. We complement these lower bounds with matching upper bounds. These are extremely rare results: it is only the second problem in NP to admit such a tight double-exponential lower bound parameterized by vc, and only one of very few problems to admit such an ETH-based conditional lower bound on the number of vertices in a kernel. For trees, interval graphs, cycles, and trees of cycles, we derive NCTM^+s or NCTMs for B(G) of size proportional to its VC-dimension, and for Gromov-hyperbolic graphs, we design an approximate NCTM^+ of size 2.