Track papers across labs, topics, and trends.
Search papers, labs, and topics across Lattice.
This paper investigates the relationship between the Vapnik--Chervonenkis dimension (VCdim) and the non-clashing teaching dimension (NCTD) for closed neighborhoods in planar graphs, proving a tight upper bound of two for NCTD and four for NCTD+. The key result establishes the conjectured inequality NCTD <= VCdim for this concept class, a fundamental open question in learning theory. Furthermore, the work demonstrates that deciding NCTD <= 1 or NCTD+ <= 1 is NP-complete, highlighting a computational hardness gap despite the established upper bounds.
Closed neighborhoods in planar graphs can be taught with at most two non-clashing examples, resolving a long-standing conjecture, yet distinguishing between one and two teaching examples is NP-hard.
Non-clashing teaching minimizes teaching complexity among models satisfying the Goldman--Mathias collusion-avoidance criterion. While the Vapnik--Chervonenkis dimension (VCdim) measures the complexity of learning from samples, non-clashing teaching dimension (NCTD) measures the number of examples required when a teacher can select them. Whether NCTD is always bounded above by VCdim remains a fundamental open question in learning theory. In this paper, we investigate this question for the concept classes of closed neighborhoods in planar graphs. We prove a tight upper bound of two on their NCTD, thereby establishing the conjectured inequality for this family. For the positive variant NCTD+, in which teaching sets contain only positive examples, we obtain a tight upper bound of four. Finally, we show that deciding whether either NCTD+ or NCTD is at most one is NP-complete, even for concept classes of closed neighborhoods in planar graphs. In particular, despite the upper bound of two on NCTD for such classes, distinguishing between NCTD values of one and two remains NP-hard.