研究图中闭邻域的非冲突教学，提升算法效率并拓展理论边界。
Non-Clashing Teaching in Graphs: Algorithms, Complexity, and Bounds
- 基于图的闭邻域设计更高效的非冲突教学算法。
- 对更广类别的图实现固定参数可追踪算法，提升计算效率。
- 适用于理解机器教学中的概念表示与复杂性边界的研究者。
Kirkpatrick 等人 [ALT 2019] 与 Fallat 等人 [JMLR 2023] 引入了非冲突教学，并证明其是满足经典碰撞规避基准的最高效批量机器教学模型。近期，正向非冲突教学在图中球体上的研究已取得丰富成果，其中 Chalopin 等人 [COLT 2024] 与 Ganian 等人 [ICLR 2025] 呈现了该变体的近乎完整复杂性图景，表明其仅在受限图类上可解，凸显问题本质难度。本文研究图中闭邻域的（正向）非冲突教学。该概念类在多个相关领域被广泛研究，且具有极强泛化能力：任意有限二元概念类均可等价表示为图中闭邻域的集合。相比球体研究，本文提出更优算法，包括对更一般参数的 FPT 算法，并辅以更强下界。最后，我们获得更广泛图类的组合上界。
原文摘要 · Abstract (English)
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.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。