# Non-Clashing Teaching in Graphs: Algorithms, Complexity, and Bounds

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

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 14 of its 47 references that are in the map.
- First posted on arXiv 31 Jan 2026.

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

- [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)
- [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)
- [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)
- [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)
- [A Faster Parameterized Algorithm for Treedepth](https://mlsanity.com/paper/1401.7540/) (2014)
- [Better Diameter Algorithms for Bounded VC-dimension Graphs and Geometric Intersection Graphs](https://mlsanity.com/paper/2307.08162/) (2023)
- [The Parameterized Complexity of Computing the VC-Dimension](https://mlsanity.com/paper/2510.17451/) (2025)
- [A Structural Complexity Analysis of Synchronous Dynamical Systems](https://mlsanity.com/paper/2312.08385/) (2023)

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

- [On Collusion-Free Teaching in Planar Graphs](https://mlsanity.com/paper/2610.18714/) (2026)

## Abstract (arXiv)

Kirkpatrick et al. [ALT 2019] and Fallat et al. [JMLR 2023] introduced non-clashing teaching and proved that it is the most efficient batch machine teaching model satisfying the collusion-avoidance benchmark established in the seminal work of Goldman and Mathias [COLT 1993]. Recently, (positive) non-clashing teaching was thoroughly studied for balls in graphs, yielding numerous algorithmic and combinatorial results. In particular, Chalopin et al. [COLT 2024] and Ganian et al. [ICLR 2025] gave an almost complete picture of the complexity landscape of the positive variant, showing that it is tractable only for restricted graph classes due to the non-trivial nature of the problem and concept class. In this work, we consider (positive) non-clashing teaching for closed neighborhoods in graphs. This concept class is not only extensively studied in various related contexts, but it also exhibits broad generality, as any finite binary concept class can be equivalently represented by a set of closed neighborhoods in a graph. In comparison to the works on balls in graphs, we provide improved algorithmic results, notably including FPT algorithms for more general classes of parameters, and we complement these results by deriving stronger lower bounds. Lastly, we obtain combinatorial upper bounds for wider classes of graphs.