[2602.00657] Non-Clashing Teaching in Graphs: Algorithms, Complexity, and Bounds

Computer Science > Computational Complexity arXiv:2602.00657 (cs) [Submitted on 31 Jan 2026 (v1), last revised 24 Mar 2026 (this version, v2)] Title:Non-Clashing Teaching in Graphs: Algorithms, Complexity, and Bounds Authors:Sujoy Bhore, Liana Khazaliya, Fionn Mc Inerney View a PDF of the paper titled Non-Clashing Teaching in Graphs: Algorithms, Complexity, and Bounds, by Sujoy Bhore and 2 other authors View PDF HTML (experimental) Abstract: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 ...