研究图中概念教学的最小示例数，揭示其计算复杂性边界。
The Computational Complexity of Positive Non-Clashing Teaching in Graphs
- 将概念教学问题转化为图中球体覆盖问题，构建理论框架。
- 证明当k=2时仍为NP难，且在一般图上存在紧致时间上下界。
- 按顶点完整性参数可固定参数可解，但按反馈顶点数等不可解。
我们研究了正非冲突教学维数的经典与参数化复杂性，即在已有模型下成功教学智能学习者所需的最小每概念示例数。对于任意概念类，该问题可自然转换为图中球体的设定。本文建立：(1) 即使在教学维数k=2且图中所有球体均存在的情况下，问题仍为NP难；(2) 一般图上的近似紧致时间上下界；(3) 当以图的顶点完整性为参数时，问题具有固定参数可解性；(4) 当以反馈顶点数和路径宽为参数，即使结合k，也不存在固定参数可解性。这些结果近乎完整刻画了该问题的复杂性景观，并回答了文献中的开放问题。
原文摘要 · Abstract (English)
We study the classical and parameterized complexity of computing the positive non-clashing teaching dimension of a set of concepts, that is, the smallest number of examples per concept required to successfully teach an intelligent learner under the considered, previously established model. For any class of concepts, it is known that this problem can be effortlessly transferred to the setting of balls in a graph G. We establish (1) the NP-hardness of the problem even when restricted to instances with positive non-clashing teaching dimension k=2 and where all balls in the graph are present, (2) near-tight running time upper and lower bounds for the problem on general graphs, (3) fixed-parameter tractability when parameterized by the vertex integrity of G, and (4) a lower bound excluding fixed-parameter tractability when parameterized by the feedback vertex number and pathwidth of G, even when combined with k. Our results provide a nearly complete understanding of the complexity landscape of computing the positive non-clashing teaching dimension and answer open questions from the literature.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。