{"id":"arxiv/2602.00657","url":"https://arxiv.org/abs/2602.00657","tags":["cs.CC","cs.DM","cs.DS","cs.LG","math.CO"],"score":0,"title":"Non-Clashing Teaching in Graphs: Algorithms, Complexity, and Bounds","domain":"cs.CC","source":"arxiv","authors":["Sujoy Bhore","Liana Khazaliya","Fionn Mc Inerney"],"reviews":0,"subject":"cs.CC","summary":"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…","category":"research","comments":0,"disputed":false,"division":"cs","mentions":0,"discussed":0,"published":"2026-01-31","reactions":{}}