# On Collusion-Free Teaching in Planar Graphs

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 8 of its 24 references that are in the map.
- First posted on arXiv 13 Oct 2026.

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

- [Sample compression schemes for VC classes](https://mlsanity.com/paper/1503.06960/) (2015)
- [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)
- [Non-Clashing Teaching Maps for Balls in Graphs](https://mlsanity.com/paper/2309.02876/) (2023)
- [Practical Computation of Graph VC-Dimension](https://mlsanity.com/paper/2405.07588/) (2024)
- [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)
- [Non-Clashing Teaching in Graphs: Algorithms, Complexity, and Bounds](https://mlsanity.com/paper/2602.00657/) (2026)

## Abstract (arXiv)

Non-clashing teaching minimizes teaching complexity among models satisfying the Goldman--Mathias collusion-avoidance criterion. While the Vapnik--Chervonenkis dimension (VCdim) measures the complexity of learning from samples, non-clashing teaching dimension (NCTD) measures the number of examples required when a teacher can select them. Whether NCTD is always bounded above by VCdim remains a fundamental open question in learning theory. In this paper, we investigate this question for the concept classes of closed neighborhoods in planar graphs. We prove a tight upper bound of two on their NCTD, thereby establishing the conjectured inequality for this family. For the positive variant NCTD+, in which teaching sets contain only positive examples, we obtain a tight upper bound of four. Finally, we show that deciding whether either NCTD+ or NCTD is at most one is NP-complete, even for concept classes of closed neighborhoods in planar graphs. In particular, despite the upper bound of two on NCTD for such classes, distinguishing between NCTD values of one and two remains NP-hard.