Non-Clashing Teaching in Graphs: Algorithms, Complexity, and Bounds
Authors: Sujoy Bhore
Liana Khazaliya
Fionn Mc Inerney
Venue: ICLR 2026 Poster (2026)
Keywords: Machine teaching
non-clashing teaching
VC-dimension
graphs
parameterized complexity
treedepth
vertex cover number
Primary area: learning on graphs and other geometries & topologies
TL;DR: We establish new results for computing the non-clashing teaching dimension in graphs, including fixed-parameter algorithms, lower bounds under the Exponential Time Hypothesis, and combinatorial upper bounds.

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 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.

Published as a conference paper at ICLR 2026
NON-CLASHING TEACHING IN GRAPHS: ALGORITHMS, COMPLEXITY, AND BOUNDS
Sujoy Bhore
Liana Khazaliya
Fionn Mc Inerney
Indian Institute of Technology Bombay, India
Technische Universität Wien Vienna, Austria
Telefónica Scientific Research Barcelona, Spain
majoy@cseiitb.ac..
eaizaalia@aa.tuwiieee
fmcinern @acinern@gmainn @gmail..mmmmmmmmmmmmm..
ABSTRACT
Kirkpatrick al. [ALT 2019] and Fallat al. [JMLR 2023] introduced non- clashing teaching and proved that it is the most efficient batch machine teaching model satisfying the Dollusion-avoidane 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 algorith- mic 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 neighbor- hoods 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.
INTRODUCTION
In classic machine learning models such as PAC-learning, a learner must reconstruct a concept C from concept class C using a random sample of examples. In contrast, in machine teaching, the examples are selected from the domain by a teacher whose goal is to aid the learner. Specifically, the teacher wants to minimize the number of labeled examples shown to the learner such that the learner can uniquely reconstruct the concept. Machine teaching is a core area in learning theory, with several models proposed in the literature (Shinohara & Miyano [991] Goldman & Kearns) 1995 Goldman
& Mathias 1996. [Balbach] 2008: Zilles et al.] |01 Gao et al. 2016; 2017 Mansouri et al. 2019).
Moreover, has many applications in machine learning, such sample compression (Kuzmin &
Warmuth 2007: Doliwa et al. 2014 Moran et al. 2015 Chalopin et al. 2022). inverse reinforce-
ment learning (Ho
2016 Brown & Nickum 2019). training data security (Mei & Zhu 2015
Zhang et al. 2018), and human-robot interaction (Thomaz & Cakmak 2009
Akgun et al. (012).
In this work, we focus on the non-clashing teaching model (Kirkpatrick et al. 2019) Fallat et al.) 2023]. batch teaching framework where the teacher presents a set of examples to the learner si- multaneously. This model has gained significant attention in recent years, since it was shown (Kirk- patrick et al. 2019: Fallat et al.) 2023) to require the fewest examples among batch teaching models that adhere to the Goldman- Mooddann-Mathiss Mathias collussionavoidaan criterion (Goldman & Mathias 1996), fundamental principle that prevents ceacher-leamne collusion (c.g., through encoding).
In non-clashing teaching, given a finite binary concept class C, a teacher maps each concept C to labeled set of examples T(C) that is consistent with C' and called the teaching set of C. The teaching map T must satisfy the non-clashing condition: for each pair of distinct concepts C, C" e C, at least one of the examples in T(C) U T(C") must be consistent with exactly one of the two concepts C and C². If satisfies this condition and maxgec [T(C)] = kt then T is a non-clashing teaching map (NCTM) of size k for C. Notably, the teacher needs to present at most k examples

---

Published as a conference paper at ICLR 2026
(specifically, T(C)) for the learner to uniquely reconstruct any concept C' E C. The non-clashing teaching dimension of C, denoted by NCTD(C), is the smallest size of an NCTM for C.
Machine teaching is often studied in the setting where the teacher is restricted to presenting only positively-labeled examples. Research in this setting dates back to 1980 (Angluin 1980a b) and has applications in, e-g.. recommendation systems (Schwab et al., 2000), grammatical inference (Stol- cke & Omohundro 1994] Denis 200T), and bioinformatics (Wang et al. [006] Yousef et al. 2008 Notably, when T TC) may only consist of positively-labeled examples for all C' E C, the correspond- ing positive non-clashing leaching dimension of C, denoted by NCTD + (C), has been extensively
studied (Kirkpatrick al. 2019 Fallat al. 2023 Chalopin et al.) 2024 Ganian et al., 2025).
The initial works (Kirkpatrick et al. 2019 Fallat et al. 2023) on non-clashing teaching studied the relationship between the NCTD and the VC-dimension (VCD), due its value in learning theory. A key open question of theirs is whether there is concept class C such that NCTD(C) > VCD(C). was also shown that deciding whether NCTD (C) < 1 (NCTD(C) S 1, resp.) is NP-complete when C is set of open neighborhoods in a graph G (Kirkpatrick et al., 2019), Although unstated, by those results, unless the Exponential Time Hypothesis (ETHi) fails, there is no algorithm running in (o(r(()-VVV(())) VVVG) time for either problem for any computable function f of the solution size k
It is known that any finite binary concept class C can be equivalently represented by a set of balls in graph G (see Fig. D. where the ball of radius
N centered at vertex v E V(G) is the set (v) == {u dist(u, v) S r. u E V(G) (Chalopin et al. 2023). This was one of two main moti- vations for the recent works (Chalopin et al. [022 Ganian et al. (025)) on non-clashing teaching for balls in graphs. The other was that this is natural and fundamental concept class that has been in- vestigated for related topics like sample compression (Chalopin et al. 2023), and its VC-dimension
is well-studied (Chepoi et al., 2007: Bousquet & Thomassé 2015 Ducoffe et al. (020).
Given graph G. a set of balls B in G. and & E N. MON-CLASH asks whether NCTD + (B) S k. I contains every ball in G, then this problem is known as STRICT NON-CLASH. When G is restricted to the class of (co-) )iipariite or split graphs. STRICT NON-CLASH remains NP-hard (Chalopin et al. 2024). even if k-
2 for the latter (Ganian et al. 2025). STRICT MON-CLASH can be solved
V(G) O(1) time, where vc(G) is the vertex cover number of G, and this is tight under the ETH (Chalopin et al. 2024]. This FPT algorithm was improved upon by considering a more general parameter and problem. as it was shown that NON-CLASHH is FPT parameterized by the vertex integrity of G (Ganian et al. 2025). As MON-CLASH is W[r]- parameterized by the feedback vertex number, pathwidth, and solution size l combined (Ganian et al. 2025), these results give nearly complete picture of its complexity landscape. There is a (P][(]") (VG)))-time algorithm for NoN- CLASH, and unless the ETH fails, there is no (n (Q) ().). -ttme algorithm, even for STRICT NCTMs are known for balls if G is tree, cycle, cactus interval graph (Chalopin al. 2024).
in 2 (2)())(())
where d is the diameter of G (Ganian et al. 2025). Finally, (hear-)optimal
Our Contributions. We explore non-clashing teaching for balls in graphs from a combinatorial and computational perspective, providing a comprehensive understanding of the problem. As discussed above, there is an inherent algorithmic intractability (NP-hard and Whil-hard). With the goal of obtaining improved algorithmic results for larger graph classes under more general parameters, we study both variants of non-clashing teaching for closed neighborhoods (balls of radius 1) in graphs:
N-NCTD
Input: A graph G. set B of closed neighborhoods in G, and positive integer k. Question: Is NCTD(B) < k?
N-NCTD+
Input: A graph G. a set B of closed neighborhoods in G, and positive integer k.
Question: Is NCTD (B) < k?
'Roughly, the ETH states that re-variable and m-clause 3-SAT cannot be solved 20(m+mm) time. "Their results are proven by reductions from matching problem in graphs. and they prove that problem is
NP-hard by reduction from variabie and m-clause 3-SAT that produces a graph with O(n m) vertices. AA problem with input size n is fixed exed-marreette tractable (FPT) parameterized by parameter p E N if admits an f(p)- n (00))-imme algorithm (i.e., an FPT algorithm) for some computable function f-
A problem that is -hard parameterized by p is not FPT parameterized by unless W[1] = FPT.
2

---

Published as a conference paper at ICLR 2026
We emphasize that this is general as studying finite binary concept classes. In fact, the afore- mentioned representation of any finite binary concept class C 2 by a set of balls in a graph G, holds for set of closed neighborhoods in G. Indeed. V(G) = V {Ic C C}. the 2 vertices form a clique, IC is adjacent to v E V if and only if u E C, and B
Mxcc | C). See Fig. [ It is also motivated by the plethora of works that have considered the VC-dimension of closed neighborhoods in graphs (Haussler & WelzI, 1987 Anthony et al. 1995; Kranakis et al., 1997 Bousquet al. 2015 Ducoffe et al., 2020 Ducoffe, 2021] Chalopin et al. [023] Coudert
et al. 2024). See (Foucaud et al. 2025) for a list of references on other graph- based concept classes.
{1.4)
(2.5)
(2,3,5)
clique
Figure 1: Graph G for a binary concept class = {[1, 4). (2, 5), (,,3,5) and B [N[C]]CEC.
In Section 2 we present improved algorithmic upper and lower bounds, which match the case of N-NCTD+ unlike in the case of VON-CLASH. Specifically, algorithmic lower bound was previously known for the NCTD of balls in graphs, however, we prove that, unless the ETH fails, there is no 2eLS(A)-iV(CI)-iim algorithm for any computable function f (Theorem 2). This also dramatically improves upon the only previously known lower bound for the NCTD of concept class, which is that, unless the ETH fails, no al. 2019). Further, our lower bound almost tight due to the 20(e-V (V(G))) algo- rithm that can be inferred from (Ganian et al. 2025). We then show that N-NCTD can be solved in (0(E()) time (Theorem 4p. and unless the ETH fails, this is tight, i.c. there is no 20(IE(G))) time algorithm (Theorem 3); fact there even no (((() -imme algorithm for any computable function f. This is also new strong lower bound for NON-CLASH.
-time algorithm exists Kirkpatrick
In Section 3 we provide two highly non-trivial algorithms prove that N-NCTD* FPT param- eterized by the treedepth of G (Theorem 5) and N-NCTD is FPT parameterized by the vertex cover number of (Theorem 7). These are two well-established structural graph parameters that have been considered in, e.g., Bayesian network learning (Korhonen & Parviainen 2015) Harviainen & Koivisto 2023) and other areas of AI (Ganian et al.) 2020 Eiben et al. 2023). Notably, we again achieve positive results that general parameter than vertex integrity and no FPT algorithm parameterized by a structural graph parameter known for any concept class when the teacher may negatively labeled examples.
not obtained in the setting of balls in graphs treedepth is more
Finally, in Section 4 we obtain combinatorial bounds for larger graph classes than those in CChalopin al. 2024). Exploiting forbidden minors, we prove that, if B is of closed neighborhoods in planar graph G, then NCTD* (B) < 7 (Theorem 12 and NCTD( I 5 (Theorem 13). Employing geometric arguments, we prove that, if B is set of closed neighborhoods in unit square graph G, then NCTD (B) < (Theorem 14p. See Table | for a summary of our results and the literature.
Table I: Summary of our results and the literature. NP-h, CN, V. E. [1], and [2] denote NP-hard, 2025). and (Chalopin al. 2024 respectively.
closed neighborhoods, VGG), E(G), Ganian et al.
NCTD Balls
NCTD* + CN
NCTD Balls
NCTD CN
Solution size
NP-h k (Th.
NP-h if (Th.
NP-h -
NP-h k- (Th.
Vertex cover
FPT [1]
FPT (Th.
FPT (Th.
Vertex integrity
FPT
FPT (Th.
Treedepth
FPT (Th.
Treewidth
Wall- [1]
Alg. up. bound
20(AA) (Th.
20tho M lolg IVD
201h (olloo
[
Alg. low. bound
2o(keddV1) VD) [1]
20(1())-M1111PP)) (Th.)
20( (Th.
2
201 (Th.
Planar
Unbounded by cycle [2]
7
< 615 [2]
S 5 (Th
13
Unit square
Unbounded by cycle [2)
<4 (Th.
< [2]
< 4 (Th.
'oor any problem on graph G, if it admits an FPT algorithm parameterized by the treedepth of G, then it admits FPT algorithm parameterized by the vertex integrity of G, but not the other way round.
3

---

Published as a conference paper at ICLR 2026
2 IMPROVED ALGORITHMIC UPPER AND LOWER BOUNDS
In this section, we first prove an algorithmic lower bound for N-NCTD that is stronger than the previous one from the literature, and then tight algorithmic bounds for N-NCTD* We begin by introducing problem-specific terminology. Let G be a graph, B a set of closed neighborhoods in G, and T a teaching map for B. If, for all B E B. T(B) S. B, then T is a positive teaching map for B. In either case, T is non-clashing for B if, for all distinct M[u), Nlu E BB there exists w E T(N(u) [u]) U T(N (e)) such that w E N [u]
U N [b] and w & N[u] n N [el; we say that w
distinguishes N and N [e]. For all E Zt, we set [n]] == [1.
n).
From the exact exponential algorithm for NON-CLASE in (Ganian et al. 2025). it can be observed that N-NCTD can be solved in 20 (G))) (V())) time. In the next theorem, we provide an im- proved lower bound, via reduction from 3-SAT, that almost matches this upper bound. However, we first need the following lemma, which will be useful for the proof of that theorem. Note that, given a graph G, two distinct vertices u, V(G) are false twins if and only if Nu)) = N()).
Lemma 1. Let G be graph with 4 pairwise false twins u1,.... u4 with N [un]..... N[wa] E B. Then, for any NCTM T of size 1 for B, there exists i E [4] such that [N,,,)) = {u.}.
Theorem 2. Unless the ETH N-NCTD cannot be solved in 20([())IVV())) time for any com- putable function f.
Proof. Given an instance yp of n-variable and m-clause 3-SAT, we construct a graph G as follows:
1. for each variable x; and clause Cj in ø, there is clause vertex cj. a variable vertex us and two literal vertices & and f; that are both adjacent to ey;
2. there is an additional dummy variable vertex up that has no adjacent literal vertices:
3. for all i E {0} U [n]] there is a set of vertices V; = {uf, of vi, ug uf) and a special vertex vf, where of is adjacent to each vertex in V,, and each vertex in Vi {or is adjacent to us;
4. for all i E [m). if the literal az (Te, resp.) is in the clause Cj in di then the literal vertex Si (li, resp.) is adjacent to the clause vertex Cj and there vertex Cj.s adjacent to us, Cj. of. and each vertex in Vi;
5. the set {c)]semm) (oshie forms elique.
This concludes the construction of G. We set B to contain the closed neighborhood of each vertex in UJ [e and Uie(oyul>) (fo,, uf) U {u/] (pe(4) (note that, for all i {0} U [n]. NoT & B). Thus, from yp, the reduction outputs the N-NCTD instance (G, (,,,B,). 1).
To show the correctness of the reduction in the first direction, let T be NCTM of size 1 for B. By Lemma] [ for all i E {0} U [n]. there exists p E [4] such that T(N[o")) = {u J. say, w.l.o.g.. fuf }. Hence, for all E (0) U [m]. T() C V, since Nlel c Mott) Therefore, for all i E [n] T(N(s)) c (N [Nss]' \ [Tz)) since Nlu]] C No:. As T(N(o))) is not adjacent to any literal vertices, then it must consist of clause or variable vertex. As the clause and variable vertices form a clique. for all i E [n]. TNN [v:)) cannot consist of a clause or variable vertex, and hence, [ex)) C (t,, fi). We extract variable assignment T: (II,... .......... 2nn] + (True, False] as follows: if ((N[)) = (t,). then T(2,) == True, and otherwise, ((x,) == False.
Toward a contradiction, suppose that 7 is not a satisfying assignment for yp. Then, there exists clause Cj in &p that is not satisfied by T. Let I', and x" be the 3 variables in Cj in & (and the corresponding variable vertices in G). By the construction of G and the definition of 7, as Cj is not satisfied, [(N(z)), [(N(')), T(N[=" [[]["]] C N(c.). Thus, as T is non-clashing for N[cy] and each of N(r), N [aa'), and N[r"], then T(N(e) consists of a vertex u E V(G), where either (1) u E N(c,). & Ma), N [arl). and u & N [a"]. or (2) u & N[c]]. u E N(2]. u E N(2'), and N[x"]. No such vertex u exists, contradicting that T is an NCTM for B. So, 7 is a satisfying assignment for s.
For the reverse direction, let {21, ( } + {True, Fa Falee} } be satisfying assignment of the given 3-SAT formula yp. We define a teaching map T for B as follows. For all i E [n]] if T(x.)= = True, then T(N
[t,). and otherwise. T(N[u,)) == (f.). For all E {0} U [n]] and p E [4], [(N == {of}. For all i E {0} U [n]. T(V()))) = {uf). For all j e [m], there exists
i [n] such that T(r))) satisfies Cj. and we set T T(N(c)) = {cg.)- Finally, T(N(vo) ((oo) (m
4

---

Published as a conference paper at ICLR 2026
We prove that is an NCTM for B. aorall i [0]U[n] and e [4] ((N = [ distinguishes
N Muffl and N Nww] for all w E ((G) such that Ni E B {N N[ For all {0} L [n] and
p E [4, T(N [x]]] distinguishes N Nlu;] and No
well as N [u; and N [7] as [(N C Nu,
T(N [c:l) I n N Mog] 0. and ((N [1s) n M = 0. For all E [0] n and p E [4], ((N(e))))
distinguishes [u,]] and [u,] since [(N(v))) C M[uf]
0. Thus, all pairs of closed neighborhoods containing N [of]] for some E [n] and p E [4] are distinguished. For all {0) U [m], Mop]]] and any other closed neighborhood in B are distinguished since T(N [(([[e]) C Mu,) but [ is not a subset of any closed neighborhood in B not already covered above.
and and (N) DN
For all distinct i [n] and q E {O]U(n) mn) T(N [Nu] and ((N and N [yy] are distinguished. For all distinct E [m], ((V[c]) C M[g and [[)le N. Teel = and so, N[e]] and N N(ee] are distinguished. For all E [x] and j E [m] such that G3 E ((N()))
0, and so, No.
((r;) satisfies the clause C₁ in s,, and so, [(N(s)) [[[c = 0, resulting in N(us] and [[g]] being
distinguished by T(N(o;)) )) For all E [n] and j E [m] such that C3S & ((N(e))), N Nu: and N [ec
[.:]).
are distinguished by 7 [[;], Lastly, for all j E [m]. [c;();)) distinguishes N [cy] and N [ub].
This completes the case analysis, and thus, T an NCTM for B.
Lastly, if N-NCTD can be solved in 2=((()))IV(()) time for a computable function f. then 3-SAT can be solved in (0(++m) time fk) = (1) and [V O()+m), contradicting the ETH. O
A similar reduction proves the following lower bound, which we then prove is tight under the ETH. Theorem 3. Unless the fails, N-NCTD cannot be solved 20(((() time for any computable function J.
Theorem 4. N-NCTD can be solved in (0(E() time.
Proof. For all E V(G). [N|]] = d(u) + 1, where d(v) is the degree of v. Therefore, there are 2d())+1 choices for (u)) So, there most (do (0( distinct positive teaching maps for B, each of which can be checked to be non-clashing or not in polynomial time. O
FIXED-PARAMETER ALGORIHTM
In this section, we prove that N-NCTD+ + is FPT parameterized by the treedepth of G and N-NCTD is FPT parameterized by the vertex cover number of G. As mentioned before, this further motivates considering closed neighborhoods instead of balls in graphs, as treedepth a more general parameter than vertex integrity (see footnote 5). and no FPT algorithm was known when the teacher may use negatively-labet labeled examples. The treedepth ta(G) of a connected graph G is the minimum height of rooted tree T such that V(T) = V(G) and, for all we E FG),, either is an ancestor of or an ancestor of u in T. The tree T a treedepth decomposition of (see Fig. for an illustration).
10
(b)
Figure 2: (a) A graph G. (b) A treedepth decomposition T of G witnessing td(G) S 4.
Theorem 5. N-NCTD+ is FPT parameterized by the treedepth of G.
We prove Theorem 5 via an algorithm that exhaustively applies a reduction rule to prune the tree T in the treedepth decomposition of G from the bottom up, yielding tree whose number of vertices is a function of (G) (see Fig. 4 From there, we compute NCTD (B) by brute force in FPT time w.r.t. td) For simplicity, the component to delete. However, the proof that it is safe (Lemma (6) specifies the component; a reduction rule is safe if the input instance is YES-instance if and only if the output instance is.
state the reduction rule in more general terms and do not specify
5

---

Published as a conference paper at ICLR 2026
Reduction Rule 1. Let G be a graph, X S VG) a subset of its vertices, and A {Ai, Ac} a subset of the connected components of G X such that maxie(e) [As] = t. If l > ([X + +t.
20IX++)2 -22++|1++1, then delete a particular connected component in A.
Lemma 6. Reduction rule 7 is safe N-NCTD
Proof Sketch. First, we give intuition. If E is large, by the pigeonhole principle, there are 3 auto- morphic components in A that are "identical" with respect to their adjacencies in X, and the closed neighborhoods of B that they contain along with their teaching sets. We select one of these 3 compo- nents, consider each teaching set that contains vertex from it, and replace that vertex by one of its two automorphic copies (made possible by their identicalness), allowing to delete that component.
Formally, let X C (G) be such that A {AA,,-.., Ar) is subset of the connected components of G-X, where max |A, = t and E> ([x]+))-2((x)+=) -(1x(+0) -2t-1x1++, Let be a positive NCTM of size most 1o for B. We first prove that there exist Ap, Aq, AR E A that are automorphic to each other and such that, for any distinct AD E (Ap,Aq, Aq.
there exists an automorphism ((Ac) - ((An) where, for all E ((Ac) and d E V(An) with (c) d, it holds that:
1. N()) n X = (())
2. N[c E B if and only if Nid] E B:
3. if N(c), N[d] E B, then T(NIc) n T(N(d) n and, for all u E (Ac) and v E V(AD)
with or (u) U, we have u E T(N(c) (V(cc) if and only if E T(N(d) n ((A)).
We prove this via the pigeonhole principle. Trivially, the number of non-automorphic graphs on at most |X| + t vertices is at most (|X) + t) 2((x+++) Thus, since é > 2(|X + there exist Ap, Aq. AR E A that are automorphic to each other and such that, for any distinct AD.AD& E {Ap, Aq. ARt. there exists an automorphism a <VAc) + V(Ap) where, for all CE (AA) and d V(A)) with (c) = d. 1. holds. Since f 2[[x] + f) -(1X)-()) 2t, we also have that 2. holds. Moreover, as l> 2([X] + t) (+))+ 2' 2 we also have that 3. holds.
2(1x)+))
we can assume exists, as otherwise we delete V(Ap). Note that w E X. We show that removing v from T(N(w)) and adding particular vertex E V(Ag) (V(R)) to [(N[w]) maintains that T is positive NCTM for B in G. Let O.Q : .(Ap) + ((A) (TP,R (AP)) + V(AR). resp.) be the automorphism between (Ap) and (AA) (V(AR). resp.). If T(N (w]) n (Aq)) 0, then
Select V(G) \ (AA) such that there exists E [[N[w]) n (AP)):
(v) and if not, but (())()) & T(N then z = (v), and otherwise no vertex is added to T(N(w))
Let T be the teaching map for B obtained from T by applying the above procedure for all w X and v E ((Ap) such that v E [(N[w). Note that T" has size at most k, and T" is positive teaching map for B since T' is, and due to property 1. above. We show that T is positive NCTM for B. Toward a contradiction, suppose there exist x, E V(G) such that T' does not satisfy the non-clashing condition for N[х] and N(y)). Due to how T" was obtained from T, and since T is an NCTM for B, while T" is not, then the only vertices in T(N xx) UT(NNN [vl) distinguishing N [xr) and N [y] are in ((Ap). Thus, w.l.o.g., v E (T(N(z)) U T(N y n ((Ap) distinguished N [sr] and
N Nly. Then, (1)) T'N ([N]))) T and/or o (c)
E T UT and, w.l.o.g., 3 Let u = (v) and u' = (
V E [xx] and v & Nly.. We do a case analysis (see Fig.
Case 1: NTO n (Ap). Thus, E [N]) distinguishes [[x] and N [y], contradiction.
Case 2: x E N(x) and y & Nuu). As N (()) = NN) = Nu then u, u' E N[x] If T'(N2z)), then distinguishes N[x] and [Bp] a contradiction. Otherwise, u' E T' [x] and there exists a vertex E (x)) n (A2). and so, since y & N(u), then y & N[w[ nx, and thus, N[x] and N[v) are distinguished by u' and/or c, contradiction.
Case 3: x E (v) n.X and y E N N[u). Thus, y E V(Aq). Let (v)) = y. As is an NCTM for B, there exists r E (x) (NN[))) that distinguishes N(x) and N(v'). We now study subcases.
Case 3.1: r E T(N[y/)). If & (Ap)), then E (Nll) distinguishes N[Ø] and Níy), a contra- diction. Ifr E V(Ap), then (p)(r)) E (NVll) distinguishes N(x) and N(y),, a contradiction.
Case 3.2: r E T(V[z)) I & (AA)), then r E [x())) If r E V(A)), then (r.)(r) E T' [N][))) and/or (r) E TN
We again study subcases.

---

Published as a conference paper at ICLR 2026
Case 3.2.1: & Ny. I & ((Ap), then r T [x]] distinguishes M2x] and Nly. a contradic- tion. Otherwise, as r E [()(x)) distinguishes M2x) [x]] and Nyy"). then r & .N My',, which implies that (r. $ NV [y]. So, rr. (r) or (r)) in (NV [x]) distinguishes [[2] and N [y], a contradiction.
Case 3.2.2: r E Myy. As T' is an NCTM for B, there exists E T [x]) (T(N [w]) distinguishing N[x]] and Nly]- r T(N(y) I.) then r' E T (N(u) distinguishes N [xr] and N Nly Hence, r'
[(N[=]). Further, if r' & Nyy",, then either r' & (Ap), and so, r' E (N [x]), or r' E ((Ap), in
which case (p")(r") (N [ai] as E [Z] [y]. In both cases, T" satisfies the non-clashing condition for N and N My]. a contradiction. Thus, r' E [Vv], and as r E [x]) n N Myv. then dp.R(r') E (MV)).)) [z). which distinguishes N [x]] and N Myy, contradiction.
Case y N Nfv/nx= Noxnnx-NNoxxx Nox
Case 3. NJu WWWjn--Nunn--Noon
X
X
X
x Ap
AQ
AR
AP
AQ
AR
Ap NastWAg)
AQ
AR
Figure 3: Cases 1, 2, and 3 in the forward direction of the proof of Lemma 6
Recall that y & Nu...
That completes the case analysis, and thus, T" is a positive NCTM for B. Let := G Ap and let B' equal B restricted to G". Since the only teaching sets of T" containing vertices in (AA)) are those of the closed neighborhoods centered in vertices of V (Ap), then T" restricted to B' is a positive NCTM of size at most l for 5' in G'. This completes the first direction of the proof.
For the reverse direction, we do the (simpler) inverse of the above. Let T' be a positive NCTM of size at most & for 13' in G'. Since there exists an automorphism Qq.R* V(AA) (AAR). then, for each * 0. Indeed,
E V ((A,) such that N Nlg] E BB', ('N((g))) (V(gg))((((A)) (Aq) o 0 and 7" otherwise T' does not satisfy the non-clashing condition for that pair of closed neighborhoods. We extend 7" to a positive NCTM I of size at most & for B in G as follows. For all p V(Ap), let p' == (p). For all E ((G)., set [=) == T (N (N(z)) and, for all p E (AP) such that [pp] E B. set [p) = (T(N(p') n X) U fo (1)). } It follows that T is a positive NCTM of size at most & for B in G due to the properties of Ap, Aq, and Ag.
Proof of Theorem 5 Use the algorithm of (Reidl et al., 2014) to compute treedepth decomposi- tion T of G of depth td(G) in 20(a)())))
[V( time. From the bottom of T up, exhaustively apply Reduction rule [ which is safe by Lemma 6 Specifically, first consider the children of a vertex at depth ta(G) 1. These children (leaves of T) form A, and their ancestors in T form X. Exhaustively apply Reduction Rule for the children of each vertex at depth td(G) - 1. Once Reduction I cannot be applied, each vertex at depth td( - 1 has at most 91 (td(G)) children, for a computable function 91. Proceeding by induction on the depth td) -j of the considered vertices, suppose that, for some 1 S < td(G), it holds that, for all 1 S j S i, after exhaustively applying Reduction Rule [ each vertex at depth td) - j has at most gj (C)) children for computable function gý- Then, exhaustively applying Reduction Rule | at depth td(G) - i results in each vertex depth td(G) - 1 having at most 9++1 (td(G) children for a computable function 95+1- See Fig. for an illustration of this pruming process. total, cxhaustively applying Reduction aa above takes FPT time with respect Gd) as we need find the components Ap, Aq. and An each time. Once Reduction rule T cannot be applied at the root of T, we have proven by induction that the remaining graph G' has at most ((t((G) vertices, and thus, at most (((ta(G)) edges, for computable functions f and f". Now, apply the algorithm of Theorem on G², which runs in f" (Ed(G)) time for a computable function f" since [E(G') = (ta(()
We proceed with the vertex cover number parameterization for N-NCTD. The vertex cover number of a graph G the minimum size of subset of vertices X S VG) such that each edge in G is incident to at least one vertex in X. We emphasize that allowing negatively-labeled examples in the teaching sets poses a significant challenge as the problem is no longer local, which can be seen by comparing the proof of the next result with the one for STRICT NON-CLASE (Chalopin et al.) 2024)
Theorem 7. N-NCTD is FPT parameterized by the vertex cover number of G.
7

---

Published as a conference paper at ICLR 2026
(((d((G))
g/ld(G))
g.(td(G))
g.(id(G))
9:(Wk))
9x(W((G
g.((()))
Figure 4: Pruning of treedepth decomposition as in the proof of Theorem
We prove Theorem 7 Via a kernelization algorithn which exhaustively applies two reduction rules. However, we first show that the solution size i can be bounded above by a function of the vertex cover number of G this is necessary condition for one of the reduction rules. To do so, consider equivalence classes for the vertices in the independent set with respect to the vertex cover. Given a graph G, let X C V(G) be vertex cover of G, and I == V(G) \ X. Any two distinct vertices u, e E I are in the same equivalence class S C I if and only if u and are false twins. Note that there are at most X distinct equivalence classes for the vertices in I with respect to X.
Lemma 8. Given graph G and a vertex cover X = V(G) of G. any B consisting of closed neighborhoods of G, it holds that NCTD(B) 2| + |X]]
Reduction Rule 2. Let G be a graph with a vertex cover X S VVG G and let = 2| If < x + |X] and there exist + 2k + 1 vertices in I == V(G) X that are pairwise false twins whose closed neighborhoods are in B, then delete one of them.
Reduction Rule 3. Given a graph G and a vertex cover X C (V) of G, if there exists a pair U V(G) of false twins in == VGG \ X such that
& B. then delete v.
The next lemma is the key to proving Reduction rule 2 is safe. Roughly, it says that if there are too many false twins in whose closed neighborhoods are in B, then, by the pigeonhole principle, two of them will have almost "identical" teaching sets. This will facilitate the deletion of one of them.
Lemma Let G be a graph with a vertex cover X S. V(G) of G, let u1,..., de be a set of pairwise false twins in the equivalence class Q of 1 == VG) \ X such that N N[u1]..... N. [ux] E B, let S 22|X + |X], and let q 22 +|X1 + For any NCTM T of size k for B, if > q + 2k,
then there exist i.j [6] such that u, T(N(u,), uj ([[Nu,)) [(Nu)) = T [NNN[,)))X
T(N[u)) n (Q) \ {u,}) = if and only if (T[(Nu,)) n (Q) {uy}) O, and [(N(u]) ns = 0 if and only Tf (u,)) n = 0 for any equivalence class S # #Q of with respect to X.
Lemma 10. Reduction rule 2 is safe for N-NCTD.
Proof. Let Q C be set of q + 2h + pairwise false twins, and let T be an NCTM of size
at most h for B. By Lemma 9 there exist u. v E Q such that u E T(N[u)). v E T(N(u)),
T(N(u) X T(N [w)) X, T(N (N (Q) {u)) = 0 if and only if
0. and TNN (v) n = 0 if and only if T(N n S = 0 for any equivalence class S & Q of with
). We show that removing v from T(N (w)) and adding E Q T(N (w]) maintains that 1' is an NCTM of size at most k for B in G. Specifically, if u & T(N T(W[W), then z = u. Otherwise, 2 is any vertex in Q \ {u, o} such that & [(N[w)) (if Q (u) C T(N(w), then no vertex is added to T(N [[w))).
respect to X. Select any vertex w E VV) (w} such that v E [u)(u)).
Let T' be the teaching map for B obtained from T by applying the above procedure for all w e V(G) \ {v) such that e T(N[w)). Note that T has size at most k. We show that T' is an NCTM for B. Toward a contradiction, suppose there exist x, E V(G) such that T" is not non- clashing for N(x) and [ly). Due how T' was obtained from T, and T is NCTM for B while 1" is not, then is the only vertex in T(M U TTTNN T(N[y) (N]]) distinguishing N [x] and N Nyy). So, E T' (N[x) U T" (N (b)) and, w.l.o.g,, V E N|æ] and & N [B). We do a case analysis (see Fig.
Case 1: x = v. Here, v E [N]) distinguishes N[x] and N N[v). a contradiction.
'A kernelization algorithm for parameterized problem 11 with input I and parameter p. runs in polynomial time and transforms an instance (I. of IT into equivalent instance (T'. .p') of IT such that [7',,'' p' < f(p), for computable function f. IT FPT parameterized by p if and only if it admits kernelization algorithm.
8

---

Published as a conference paper at ICLR 2026
Case 2: x E (t) and y # As M & Nlu, and false twins, and y * u, then u E [2x] and u & Ny.. So, u E TT (N'p) (ul) distinguishes M[x] and N [y]. a contradiction.
(u) and y As in Case 2, it must be that N [x]. Since NN [xr] there cxists r E (T(M[z]) ((V))))) {v} that distinguishes Maa] and N [u]. We now study subcases.
Case 3:
Case 3.1: r. T(N Here, r (NN distinguishes M[x] and Nuu), contradiction.
Case 3.2: r E [(N S for an equivalence class S of I with respect to X. If r = u, then S = and there exists 2 E (NTu) n Q) {u, o} that distinguishes [[x] and N [u], contradiction.
Otherwise, there is E (T" ris) \ {u, o} that distinguishes N [ax] and . [u]. a contradiction.
Case 3.3: [()(=)) In this case, r E (x))) If r # u, then y E (N]))) distinguishes [[x] and Mu,, a contradiction. Otherwise, r = u. Since we have dealt with all the other cases, we further assume that u is the only vertex in (T(N(z)) U ((N))))) {v} that distinguishes
N [ and N ME... Due to this property of r and the fact that T satisfies the non-clashing condition
for Maa] and N N(u]. either E T(N [=r) or some vertex r' T(N [u]) \ {u} distinguishes N[a]
and Mu,. In the former case, as u, E [(N[z)). there exists 2 E (TV()))) nQ) {u, v} that distinguishes [(x] and N Mul. a contradiction. In the latter case, if * v, then r' also in (NV [u]), and so, it distinguishes [[x] and N [(u), a contradiction. Otherwise, r' = v, and hence, there exists E (N))) QQ) {u, # that distinguishes N [xx] and Mul). a contradiction.
Case 1.
N())
Case y a N(O)-(()
Case 3.
N(V=NOW
X
x
v=x
U
Q
Figure 5: Cases 1, 2, and 3 in the forward direction of the proof of Lemma 10 Recall that & Nuu].
That completes the case analysis, and thus, T is an NCTM for B. Let G' == G {b} and let B' equal B restricted to G'. Since the only teaching set of containing v is [(N(u)). then T" restricted to B' is an NCTM of size at most & for B' in G'. This completes the first direction of the proof.
For the reverse direction, let T' be an NCTM of size at most l for B in G'. By Lemma 9 there exists E V(G") such that u E [N])) and and are false twins in G. Adding to G does not make any two closed neighborhoods that were the same in G' become distinct in G. Hence, it
sufficient extend T' to NCTM T of size most k for B in G as follows. Set T(N [u]) ==
(v) U (T'(N[u) \ {u}), and, for all x E V(G",, set T(N [x]) == (N)) Note that T has size at most We now show that T an NCTM for B in G. As T(N[z)) = [==] for all E ((G"), we only need to show that T' distinguishes [[v] and Nly] for all E V(G) {v} such
that Nly] E B3. Since v E T(N(w)), T satisfies the non-clashing condition for N(v) and N for any & N N(p.. Otherwise, y E X n (v)). If E T' (N(u) distinguishes N(u and N(v)). then x * since u E N[y] as u and e are false twins, and thus, x is also in [vl and distinguishes N(v) and N [w]. Otherwise, x E T'N [w]) distinguishes N [u] and N [w)] but + and thus, E T(N()) also distinguishes [ly and Nuv. Hence, T is an NCTM of size at most i for B in G.
Lemma 11. Reduction rule iis safe for N-NCTD.
Proof of Theorem 7 Use the classic polynomial-tine algorithm to compute a 2-approximate min- imum vertex cover X C (G). By Lemma k: > -| + |X], then it is a YES-instance. Otherwise, exhaustively apply Reduction rules and 3 which do not alter & and are safe by Lem-
mas TO and I1 This a kernelization algorithm as it takes polynomial time and the resultant graph
has at most 2 X + 2k) + 2| + |X| < 21x ( XI + x + 2|x + |X] vertices.
L
4 COMBINATORIAL UPPER BOUNDS FOR GRAPH CLASSES
We finish by providing upper bounds on the (positive) non-clashing teaching dimension for closed neighborhoods B of graph G when G is restricted planar or unit square graphs. Note that upper bounds for any B hold for any B' C B, and VCD(B) & 4 in both cases Duraa et al. 2024).
Theorem 12. For any planar graph G, if B (N(v) V V(G),, then NCTD (B) < 7.
9

---

Published as a conference paper at ICLR 2026
Proof. We construct positive NCTM T of size at most 7 for B. For all V(G), if d(v) 6, then set T(N == Muj. Otherwise, for each v E V(G) with d(u) 2 7, place any neighbors of in ( [ul). Consider any one such vertex and let 01 U2, 2y be its 3 neighbors in [e)). Since G is planar, there is at most one other vertex E ((G) such that vn, f2, 0a E (u), as otherwise there would be K3,3- Hence, 7 satisfies the non-clashing condition for Nuj and N[2] for all {v, u, 01, U2, V33 if u exists, and for all x E V(G) (1,01, U2 J3 otherwise.
E V(G)
As long as there exists a pair [i,, N [y] E such that d(v) 2 N(u + NWy, and T does not currently satisfy the non-clashing condition for the pair, then there exists w E (N[e] \ N Nwl) U (Nyy) \ Nlo)) that will be added to [<N(e)) or [yl to distinguish the pair. Specifically, w E M[j \ [[). then add w to [N)) and otherwise, add w N Nyyl [[] to ((V)))) In either case, then satisfies the non-clashing condition for Nu and N(y). Once this process completed, T is positive NCTM for B as it is non-clashing for [[v] and N N(y] for any vertex with d(v) 2 7, but also for the closed neighborhoods of any two vertices of degree at most since their teaching sets coincide with their closed neighborhoods in this case. For each u E V(G) with d(v) > 7, as there were at most 4 possibilities for y (the vertices corresponding to u, 1 02 and Vy above), then most 4 vertices were added to any teaching set during this process. Thus, T has size most D
Theorem 13. For any planar graph G, if B = [N[d] E V(G),, then NCTD(B) S 5.
We end with unit square graphs: the intersection graphs of axis- scis-parallel unit squares in the plane. Theorem 14. For any unit square graph G, if B {N [b] V(G),, then NCTD (B) S 4.
Proof. We construct positive NCTM T of size at most for B. For all e E VG),, let R(v) be the minimum rectangle enclosing [(v] in the plane (see Fig. 6). If square does not intersect v, then for one of the directions left, right, up, or down, a is farther in that direction than a square contained in R(v) that is the farthest in that direction. Thus, is not contained in R(v), and each square in R(v) intersects v. For all v E (G), [[] consists of the vertices represented by the leftmost, rightmost, topmost, and bottommost squares R(v) (they may not be unique). Consider any u V(G) (u). If R(u) F R(v), then there exists x E T(N [u]) ((N(e)) that distinguishes N and Mju]. Indeed, w.l.o.g., say that part of R(u) ) is farther the left than all of R(v); then, x E T(N(ul) is the leftmost square in R(u), and & N [v] as part of R(u) is farther to the left than all of R(v). If R(u)= R(v), then [u] = N [u] as each square in R(v) (R(u), resp.) intersects v (u, resp.).
R(())
R(())
Figure 6: In the proof of Theorem 14 the minimum rectangles R(u) (blue) and R(v) (red) enclosing
N Nuu and Nou), respectively. The leftmost square R(u) (w1 T(N[ul)) not contained in R(v).
5 CONCLUSION
We studied non-clashing teaching for closed neighborhoods in graphs, notably providing highly non-trivial FPT algorithms and strong algorithmic lower bounds. Several open directions remain for future work, such as exploring the complexity with respect to treewidth or planarity for N- NCTD and N-NCTD, as well as vertex integrity and treedepth for N-NCTD. However, like NoN- CLASH (Ganian et al. 2025). we expect that they are W[1]-hard parameterized by the treewidth. also important determine whether Theorem 13 is tight, since the balls of planar graph has been mentioned (Chalopin et al. 2024) as a potential concept class negatively answering the question of (Kirkpatrick et al. 2019 Fallat et al. 2023), i.e., such that NCTD(C) VCD(C).
10

---

Published as a conference paper at ICLR 2026
ACKNOWLEDGMENTS
This work was partially supported by the Austrian Science Fund (FWF) [10.55776/Y1329 and 10.55776/COE12), the WWTF Vienna Science and Technology Fund (Project (044737//CT22222), the European Union's Horizon 2020 research and innovation COFUND programme Log- iCS @ TUWien (grant agreement No 101034440), and the Smart Networks and Services Joint Un- dertaking (SNS JU) under the European Union's Horizon Europe and innovation programme under Grant Agreement No. 101 139067 (ELASTIC), Views and opinions expressed are however those of the authors only and do not necessarily reflect those of the European Union (EU). Neither the EU nor the granting authority be held responsible for them.
REFERENCES
Baris Akgun, Maya Cakmak, Jae W. Yoo, and Andrea L. Thomaz. Trajectories and keyframes for kinesthetic teaching: A human-robot interaction perspective. In Proc. of the 7th ACM/IEEE Internal. Conf. on Humann-Roool Interaction (HR! 2012), pp. 391-398, 2012.
Dana Angluin. Inductive inference of formal languages from positive data. Information and Control, 45:1 17-135, 1980a.
Dana Angluin. Finding patterns common set of strings. Journal of Computer and System Sciences, 11:46-62, 1980b.
Martin Anthony, Graham R. Brightwell, and Colin Cooper. The of a random graph. Discrete Math., 133(4-3):3-56,, 1995.
dimension
Frank J. Balbach. Measuring teachability using variants of the teaching dimension. Theoretical Computer Science, 397(1-3):94-13, 2008
Nicolas Bousquet and Stéphan Thomassé. VC-dimension and Erdös-Pósa property. Discrete Math- ematics, 338:2302-2317, 2015.
Nicolas Bousquet, Aurélie Lagoutte, Zhentao Li, Aline Parreau, and Stéphan Thomassé. Identifying codes in hereditary classes of graphs and VC-dimension. SIAM Journal on Discrete Mathematics, 2944):2047-2044, 2015.
Daniel S. Brown and Scott Niekum. Machine teaching for inverse reinforcement learning: Al- gorithms and applications. In Proc. of the 33rd AAAI Conference on Artificial Intelligence (AAAI 2019), volume 33, pp. 7749-7758, 2019.
Jérémie Chalopin, Victor Chepoi, Shay Moran, and Manfred K. Warmuth. Unlabeled sample com- pression schemes and corner peelings for ample and maximum classes. Journal of Computer and System Sciences, 127:1-28, 2022.
Jérémie Chalopin, Victor Chepoi, Fionn Mc Inerney, Sébastien Ratel, and Yann Vaxès. Sample compression schemes for balls in graphs. SIAM Journal Discrete Mathematics, (7(4:22585- 2616, 2023.
Jérémie Chalopin, Victor Chepoi, Fiom Mc Inerney, and Sébastien Ratel. Non-clashing teaching maps for balls in graphs. In Proc. of the 37th Annual Conference on Learning Theory (COLT 2024), volume 247 of Proceedings of Machine Learning Research, pp. 840-875, 2024.
Victor Chepoi, Bertrand Estellon, and Yann Vaxès. Covering planar graphs with fixed number of balls, Discrete Computational Geometry, 37:237-244 2007.
David Coudert, Mónika Csikós, Guillaume Ducoffe, and Laurent Viennot. Practical computation of graph VC-dimension. Proc. of the 22nd International Symposium on Experimental Algo- rithms (SEA 2024), volume 301 of L.Ples, pp. 8:1-8:20. Schloss Dagstuhl- Leibniz-Zentrum für Informatik, 2024.
François Denis. Learning regular languages from simple positive examples. Machine Learning. 44:
37-66, 2001.
11

---

Published as a conference paper at ICLR 2026
Thorsten Doliwa, Gaojian Fan, Hans Ulrich Simon, and Sandra Zilles. Recursive teaching dimen- sion, VC-dimension and sample compression. Journal of Machine Learning Research, 15(1): 3107-3131, 2014.
Guillaume Ducoffe. On computing the average distance for some chordal-like like graphs. In Proc. of the 46th International Symposium on Mathematical Foundations of Computer Science (MFCS 2021), volume 202 of LIPIcs, pp. 44:1-44:16. Schloss Dagstuhl- Leibniz-Zentrum für Informatik, 2021.
Guillaume Ducoffe, Michel Habib, and Laurent Viennot. Diameter computation on H-minor free graphs and graphs of bounded (distance) VC-dimension. In Proc. of the 31st Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2020), pp. 1905-1922, 2020.
Lech Duraj, Filip Konieczny, and Krzysztof Potepa. Better diameter algorithms for bounded vc- dimension graphs and geometric intersection graphs. In Proc. of the 32nd Annual European Symposium on Algorithms (ESA 2024), volume 308 of LIPlcs, pp. 51:1-51:18. Schloss Dagstuhl -eebbniz-Zentrum für Informatik, 2024.
Eduard Eiben, Robert Ganian, Thekla Hamm, and Viktoriia Korchemna. A structural complexity analysis of synchronous dynamical systems. In Proc. of the 37th AAAI Conference on Artificial Intelligence (AAAI 2023), pp. 6313-6321, 2023.
Shaun Fallat, David Kirkpatrick, Hans U. Simon, Abolghasem Soltani, and Sandra Zilles. On batch teaching without collusion. Journal of Machine Learning Research, 14:40:1-40:33: 2023.
Florent Foucaud, Harmender Gahlawat, Fionn Mc Inerney, and Prafullkumar Tale. The parameter- ized complexity of computing the VC-dimension. In Advances in Neural Information Processing Systems (NeurIPS 2025), volume 38, 2025.
Robert Ganian, Tomáš Peitl, Friedrich Slivovsky, and Stefan Szeider. Fixed- Parameter Tractability of Dependency QBF with Structural Parameters. In Proc. of the 17th International Conference on Principles of Knowledge Representation and Reasoning (KR 2020). pp. 392-402, 2020.
Robert Ganian, Liana Khazaliya, Fionn Me Inemny, and Mathis Rocton. The computational com- plexity of positive non-clashing teaching in graphs. In Proc. of the 13th International Conference on Learning Representations (ICLR 2025), 2025.
Ziyuan Gao, Christoph Ries, Hans U. Simon, and Sandra Zilles. Preference-based teaching. In Proc. of the 29th Conference on Learning Theory (COLT 2016), volume 49 of JMLR Workshop and Conference Proceedings, pp. 971-997. 2016.
Ziyuan Gao, Christoph Ries, Hans U. Simon, and Sandra Zilles. Preference-based teaching, Journal of Machine Learning Research, 18:1-32 2017.
Sally A. Goldman and Michael J. Kearns, On the complexity of teaching. Journal of Computer and System Sciences, (01):30-3,, 1995.
Sally A. Goldman and H. David Mathias. Teaching a smarter learner. Journal of Computer and System Sciences, 52(2):255-26) 1996.
Juha Harviainen and Mikko Koivisto. Revisiting Bayesian network learning with small vertex cover. In Proc. of the 39th Conference Uncertainty in Artificial Intelligence (UAI 2023), volume 216, pp. 819-828, 2023.
David Haussler and Emo Welzl. Epsilon-nets and simplex range queries. Discrete & Computational Geometry, 2:127-151, 1987.
Mark K. Ho, Michael Littman, James MacGlashan, Fiery Cushman, and Joseph L. Austerweil. Showing versus doing: Teaching by demonstration. In Advances in Neural Information Process- ing Systems (NeurIPS 2016), volume 29, pp. 3027-3035, 2016.
David Kirkpatrick, Hans U. Simon, and Sandra Zilles. Optimal collusion-free teaching. In Proc. of the 30th International Conference on Algorithmic Learning Theory (ALT 2019), volume 98 of Proceedings of Machine Learning Research, pp. 506-528, 2019.
12

---

Published as a conference paper at ICLR 2026
Janne H. Korhonen and Pekka Parviainen. Tractable Bayesian network structure learning with bounded vertex cover number. In Advances in Neural Information Processing Systems (NIPS 2015), volume 28, pp. 622 630. 2015.
Evangelos Kranakis, Danny Krizane, Berthold Ruf, Jorge Urrutia, and Gerhard J. Woeginger. The VC-dimension of set systems defined by graphs. Discrete Applied Mathematics, 77(3)2237-277, 1997.
Dima Kuzmin and Manfred K. Warmuth. Unlabelled compression schemes for maximum classes. Journal of Machine Learning Research, 8:2047-2081, 2007.
Farnam Mansouri, Yuxin Chen, Ara Vartanian, Jerry Zhu, and Adish Singla. Preference-basee batch and sequential teaching: Towards a unified view of models. In Advances in Neural Information Processing Systems (NeurIPS 2019), volume 32, pp. 9195-9999000 2019.
Shike Mei and Xiaojin Zhu. Using machine teaching identify optimal training-set attacks on machine learners. In Proc. of the 29th AAAI Conference on Artificial Intelligence (AAAI 2015), volume 29, pp. 2871-2877, 2015.
Shay Moran, Amir Shpilka, Avi Wigderson, and Amir Yehudayoff. Compressing and teaching for low VC-dimension. In Proc. of the 56th Annual IEEE Symposiun Foundations of Computer Science (FOCS 2015), pp. 40-51, 2015.
Felix Reidl, Peter Rossmanith, Fernando Sánchez Villaamil, and Somnath Sikdar. A faster param- eterized algorithm for treedepth. In Proc. of the 41 International Colloquium Automata, Languages, and Programming (ICALP 2014), volume 8572 of Lecture Notes in Computer Sci- ence, pp. 931-942. Springer, 2014.
Ingo Schwab, Wolfgang Pohl, and Ivan Koychev. Learning to recommend from positive evidence. In Proc. of the 5th International Conference on Intelligent User Interfaces (IUI 2000), pp. 241-247, 2000.
Ayumi Shinohara and Satoru Miyano. Teachability in computational learning. New Generation
Computing, 8:337-347, 1991.
Andreas Stolcke and Stephen Omohundro. Inducing probabilistic grammars by Bayesian model merging. In Proc. of the 2nd International Colloquium on Grammatical Inference (ICGI 1994), pp. 106-118, 1994.
Andrea L. Thomaz and Maya Cakmak. Learning about objects with human teachers. Proc, of the 4th ACM/IEEE Internat. Conf. on Human-Robol Interaction (HRI 2009), pp. 15-22, 2009.
Chunlin Wang, Chris Ding, Richard F. Meraz, and Stephen R. Holbrook. PSoL: positive sample only learning algorithm for finding non-coding RNA genes. Bioinformatics, 22(21):2590-2555 2006.
Malik Yousef, Segun Jung, Louise C. Showe, and Michael K. Showe. Learning from positive ex- amples when the negative class is undetermined microRNA gene identification. Algorithms for Molecular Biology, 3(2), 2008
Xuezhou Zhang, Xaiojin Zhu, and Stephen Wright. Training set debugging using trusted items. In Proc. of the 32nd AAAI Conference Artificial Intelligence (AAAI 2018), pp. 4482-4489, 2018.
Sandra Zilles, Steffen Lange, Robert Holte, and Martin Zinkevich. Models of cooperative teaching and learning. Journal of Machine Learning Research, 12:349-384 2011.
13

---

Published as a conference paper at ICLR 2026
A APPENDIX
A.1 SUPPLEMENTARY FIGURE
Step I: by Lemma Vi (0) U [m]. T() (of)) for some [4]
Step 2: by Step vs E (0) U (n). T(M C.
O
Step by Step 2, [ool) clause or variable
Step 4: Steps and Wi [m]. T(N[e4) (4+ fa)
Vo
Step 5: by Step 4, Vjj E [mm..fiiy = Va"),
100
then [(Nle;)) C
} (however, some exceptions are possible)
1
21
fi
V1
10
12
1,1
22
f2
2
V2
1/2
02
02
t3
f3
C1.3
C2
V/
4.
f4
C2
14
VA
Figure 7: Example of the graph G constructed in the proof of Theorem with o V V233
(I2 V xy V x4) in the 3-SAT instance. The two bold rectangles together form clique. The edges going from vertices in one of the two large dashed rectangles to vertices in the other are omitted for legibility. Only the closed neighborhoods of filled vertices are in B.
14

---

Published as a conference paper at ICLR 2026
A.2 PRELIMINARIES
All considered graphs are connected and simple. Given a graph G and u E V(G), N(u) = {x wv E } is the open neighborhood of and Muj ((u) U {u} is its closed neighborhood.
A.3 PROOF OF LEMMA
Proof. If no NCTM of size 1 for B exists, then the statement trivially holds. So, let 7 be an NCTM of size for B. When only considering M[uiJ...,, [uuu] from B, for any E [4] and E T(N[ua) [[[[s)),
if u = Us then only distinguishes [ua] and [uy] for all j E [4] \ {i]:
if u = " for some j E [4] \ {+}, then v only distinguishes Mu, and N(uy]:
u {w,,..... ua) then e does not distinguish [u,,] and M(uy] for any j E [4] \ (i).
Toward contradiction, suppose that [u:l) + { for all E [4]. By the above analysis, for all ? E [4]. the sole vertex in [(N]uu] distinguishes N [u,]] and at most one other closed neighborhood in {N[ut),... N [ua]} [N[u.]]: As there are 4(3)/2 6 such pairs that need to be distinguished,
T does not satisfy the non-clashing condition for some pair in (M(u), N...,,Nuu Muu4]. a contradiction.
Thus, there exists E [4] such that [[][ss) (u.).
A.4 PROOF OF THEOREM 3
Step 1: Vi [m], T(N[ee)) C (t. fi) distinguish N[v.] & [o;]
d
Step 2: Vj [m], T(N(s)) N(e)) \ (ef)) J distinguish N|cyl N N(c]]]
2,
C22
C2,3
f1
fa
fa o
U3
v1
t2
022
f3
0/g
1/2
t4
44
t3
C1,1
C1
C1,4
d
C1
Figure 8: Example of the graph G constructed the proof of Theorem with y = (x1 22 V A
(x) V T7 V æz) in the 3-SAT instance. Only the closed neighborhoods of filled vertices are in B.
Proof. Given an instance ip of n--ariiall and m-clause 3-SAT, we construct graph G as follows:
for each clause Cj di there a clause vertex ej adjacent to pendent vertex cf;
for each variable x; in é, there is a variable vertex e; adjacent a vertex vi as well as two literal vertices t; and fú:
for all i E [m]] if the literal æ, (F, resp.) contained in the clause C, Φi, then the literal vertex Ja (4,, resp.) is adjacent to the clause vertex ez;
for all E [m] and E [m] such that ey is adjacent to I, or fú. there is vertex Cj. adjacent to es 8/. and cj-
This concludes the construction of (see Fig. g We set to contain the closed neighborhood of each variable vertex v;, each clause vertex çj and each of their pendent vertices of and cy. So. from e, the reduction outputs the N-NCTD- instance (G, B, 1). We prove the reduction is correct.
15

---

Published as a conference paper at ICLR 2026
Let T be a positive NCTM of size 1 for B. For all E [n], T(NTe)) C {tz, fs as Mee Nu; and Mu, \ NN = ft). We extract a variable assignment T: (Ii,..., + False] as follows: if ([Ve]) = [ti), then r(2;) True, and otherwise, T(2;) False.
Toward a contradiction, suppose that T is not a satisfying assignment for yp Then, there exists a clause Cý in op that is not satisfied by т. Let x; x², and x" be the 3 variables in Cj in to (and the 3 corresponding variable vertices in G). Since C₁ is not satisfied, [>)[x)), T(N [x'I), (NV=") c
N Nej] by the construction of G and the definition of Thus, T' non-clashing for Meş and each of N Mrr) N [x'), and N [a"", J. then [(N[c)) must consist of a vertex E ((G) such that u E N Mcs]. $ [xx] & M[='), and u & N[x"]. is easy to check that the only possibilities for such a vertex are Ej and cy. However, T(N(e)) & (eg, 23} since Mcç = {eg, C Meyl as otherwise T does not satisfy the non-clashing condition for M(cy] and N [c.]. Hence, this contradicts that T is an NCTM for B. Therefore, r is a satisfying assignment for yp.
For the reverse direction, let :: {Ii..... ] + {True, False] } be a satisfying assignment of the 3-SAT formula yp. We define a positive teaching map T for B. For all E if (xx)) True, if
then T(N
[s])) := -(4,), and otherwise, T(N(s;) == {Li}. For all i E [n]. ((M)))) == {v)) For
all j E [m]. there exists E [rx] such that T T(xg)) satisfies Cj. and we set [(N(c))) = {eg,)) Lastly,
for all j
T(M[c))
{c We now prove that T is positive NCTM for B.
For all i E [n]. T(N [v:) N 0, and thus, T(N (s))) distinguishes N [v:]] and Mug] Moreover, for all E [n]. T(N (o1] = ii distinguishes N[e]] and all the other remaining closed neighborhoods in B. For distinct i, f E [nx]. [(V().)) distinguishes N Nu: and [[v) since T(N [u.]) n N [ey] O. By symmetric arguments, for each j E [m]] T satisfies the non-clashing condition for N Mic,i and any other closed neighborhood in B, as well as any pair of closed neighborhoods of clause vertices.
For all E [n] and j E [m]] such that Cja E T(N(,,)) T(x;) satisfies the clause Cj in y,, and thus, N[N = 0, resulting in N [us] and N[cy] being distinguished by T(N[u:)) For all i [n] and j E [m]] such that Cj.a $ T ((N(s)) Nus] and N N[cy] are distinguished by T(Nee)). The case analysis is complete, and so, T is positive NCTM for B.
Finally, note that both |V(G)| and [F()) are linear in the number of variables and clauses in the 3-SAT instance yp So, if N-NCTD can be solved in ((V((()))(V(())))))))))()()))))) function f. then 3-SAT can be solved in 20(n-m) time as f(k) = (1), contradicting the ETH. C
time for a computable
A.5 PROOF OF LEMMA 6
Note that only the reverse direction in this proof differs from the proof sketch in the main text.
Proof. First, we provide intuition. If é is large, by the pigeonhole principle, there are 3 automorphic components in A that are "identical" with respect to their adjacencies X, and the closed neigh- borhoods of B that they contain along with their teaching sets. We select one of these 3 components, consider each teaching set that contains a vertex from it, and replace that vertex by one of its two automorphic copies (made possible by their identicalness). allowing that component to be deleted.
Formally, let X S (G) be such that A = {A .d) is a subset of the connected components of G-X, where max |A, t and f > (IX)+ 2(x 121-1x1+1 Let T be a positive NCTM of size at most is for B. We first prove that there exist Ag. Ar E A that are automorphic to each other and such that, for any distinct Ac, AD E (Ap, Aq, An). there exists an automorphism a: (AAc) - ((A)) where, for all e E (AA)) and d V(An) with (c) d, it holds that:
1. N((c) n X ((dd)x)
2. .Tc E B if and only if N(d E B:
3. if [[c], Nid] E B, then T(N()) nx T(N(d) n and, for all u E ((Ac) and E V(Ap)
with a (u) v, we have u E T((Ncc) nV) if and only if E T(N(d) n V(Ap).
We prove this via the pigeonhole principle. Trivially, the number of non-automorphic graphs on at most |X| + vertices is most (|X) + +t) x Thus, since é > 2([X + -
there exist Ap, Aq. Ar E A that are automorphic to each other and such that, for any distinct Ac, Ad E {Ap, Aq, AR), there exists automorphism V(Ac) + V(Ap) where, for all
16

---

Published as a conference paper at ICLR 2026
E V(Ac) and d ((A)) with (c) d, 1. holds. Since / > 2[|X] + +t) --)-211 -2(11)10² 2 we also have that 2. holds. Moreover, as l > 2[|x]] + t).
2((1++)) 22 - we also have that 3. holds.
Select w E V(G) \ ((Ap) such that there exists v E T(N n (Ap)); we can assume exists, as otherwise we delete V(Ap). Note that w E X. We show that removing v from [(N and adding a particular vertex E ((Ag) (V(R)) to [(N[w)) maintains that T is positive NCTM for B in G. Let P.Q ((AAp) + V (A2) (ap.n : (AAp) - V(AR), resp.) be the automorphism between (AAp) and ((Ag) (V(AR), resp.). If (PT(NWw)) n (Aq) = 0. then
(v)) and if not, but (P) & T(N [w]). then 2 = (P).(v), and otherwise no vertex is added to T(M[w]
Let T" be the teaching map for B obtained from T by applying the above procedure for all w E X and v E (AA)) such that v E T(M[w).. Note that T" has size at most k, and T" is a positive teaching map for B since T is, and due property 1. above. We show that T' is positive NCTM for B. Toward a contradiction, suppose there exist æ, y E V(G) such that T does not satisfy the non-clashing condition for N [[r] and N Nly). Due how T was obtained from T, and since T is an
NCTM for B, while T" is not, then the only vertices in T N [x]] (T(N[y) distinguishing N [ and
N [y] are in (AAp). Thus, w.l.o.g.. U E (T(N U T N y ) (Ap) distinguished N [r]] and and, w.l.o.g.,
N [u] Then, (v) E (N [T)N())) (y]) and/or OP (v) E (M)))))
V E [x]] and v & Myy. We do case analysis (see Fig. Let u = (v) and u' = (v))
Case 1: x E N[] n (Ap). Thus, V E ('(N(z) distinguishes N and N|u], a contradiction.
Case 2: E N(6) and y & N(u]. As (w) = N( = (w'') n
X, then u, u' E Mwx Hence, u', u or vertex in (N[])) n V(Aq) distinguishes [xc] and N [g]. a contradiction.
Case 3: E (N)) nx and y E N [u]. Thus. y E V(A)), Let P. (1') = y. As i' an NCTM for B, there exists r E [(N[=)) UT(N[')) that distinguishes N [xx] and [wv]]. We now study subcases.
Case 3.1: E T(N(w))). Here, r E [wll)) distinguishes Max] and N [w]. a contradiction.
Case 3.2: r E [(]]=)). If r & ((Ap), then r E T'())=)). Ifr r E V(Ap), then dP.)(r) E [=]) and/or (T) E T (<]x)) We again study subcases.
Case 3.2.1: r & My.. I & V (AP),, then r E T" [=]) distinguishes [xx] and N Myy) a contradic- tion. Otherwise, as [=]) distinguishes N [x]] and N NIy/). then $ N [y']. which implies that (P.Q(r) & Nly. So, (r) or (p.)(r) in (N)))) distinguishes N[2] and N Nlyl, a contradiction.
Case 3.2.2: r E Nly]. As T is an NCTM for B3 there exists r' E [Z) UTN[[)] [y]) distinguishing [[x] and N Nly] rf [(N(x)). Further, r' & NNyl then either & ((rr), and so, r' E T' (N [=))). or r' E VA in which case (r)n(r') ('(N(() ( a E (N [y]. In both cases, T' satisfies the non-clashing condition for N [[x] and N Nly]. a contradiction. Thus, r' E [wv]], and as r E [x)) n NN]).. then (P)R(r") E (NV[())) [z]), which distinguishes N [xr] and [(v), contradiction.
E [M)) then r' E T" (N(()))) distinguishes N [x]] and N Hence, r' e
That completes the case analysis, and thus, T" is a positive NCTM for B. Let G' : G Ap and let E' equal B restricted to G². Since the only teaching sets of T" containing vertices in V(Ap) are those of the closed neighborhoods centered in vertices of (Ap), then T" restricted to B' is a positive NCTM of size at most & for B' in G". This completes the first direction of the proof.
For the reverse direction, we do the (simpler) inverse of the above. Let T' be a positive NCTM of size at most l for 13' in G'. Since there exists an automorphism fQ. : ((Aq) + (AAR). then, for each q E ((A,) such that N N[q] E B3, ('(NN))) # 0 and [N (N(()),RR)))) R( (AR)= + V. Indeed, otherwise T" does not satisfy the non-clashing condition for that pair of closed neighborhoods. Note that the addition of V (Ap)
) to G' does not make any two closed neighborhoods that were the same positive NCTM T of size at most & for B in G as follows. For all p E ((Ap), let p' == dp.((p). For all x E (G'), set T(N[=)) == (N [x]), and, for all p E V(Ar) such that N(p) E B, set T(N = (T(NP'') n
in G' become distinct in G. Hence, it is sufficient to extend T"
U (WT (Aa) (A4) (1))
Note that T has size at most and is a positive teaching map for B. We now show that 7 a positive NCTM for B in G. Since T(N[=)) := [2])(z)) for all x E VG'),, we only need to show that T distinguishes .N [pp and Nly] for all p E (AA) and y E (G) such that N Nip,, N NNy] E B. For all p E V (Ap), since ([N]p) n (Ap) / 0, T satisfies the non-clashing condition for N [p] and N [v]
for any y & (A(Ap) U (p) n X)). We now proceed with a case analysis.
17

---

Published as a conference paper at ICLR 2026
distinguish Norr:( (v)] and N(p'). I E X. then I E (p) u ((Nl distinguishes N [p] and Myy.. Otherwise, I E V(Aq), and thus, 02.001/2100 (x) E ((N U (yll)) distinguishes [[p] and Nyy-
Case 1: y E ((Ap) (p). Let e (N
Case 2: y E (())nx. I E (N') distinguishes N[p and M(y]. then either & E T(Np))) or x: E V(Ag) and (p)(2)) E T(Np)) In both cases, T satisfies the non-clashing condition for N[p] and Myy.. Otherwise, I E (VV)))) distinguishes [Tp and Nlv]. Since x & NTpl and (N (yl) (Ap) = 0. then x & N [p). and thus, 2 T(N [y]) distinguishes Npp and N
This completes the case analysis. Hence, T is a positive NCTM of size at most ls for B in G.
C
A.6 PROOF OF LEMMA g
Proof. It suffices to prove it for B [M[b E V(G) as the upper bound then holds for all B' S B. We construct an NCTM T of size at most 2| + [X] for B. Let Si...., SS be the distinct equivalence classes of size at least 1 of := := V(G) X with respect to X. For each x E X, set [(N[x)) == X U (sI...., Sp] U (ti...., 1p), where 8; and f, are any two distinct vertices in S; for all i E [p] (if [S:] = 1, then say that 6, does not exist). For each y E L, set T(N == X U (v). Since p < 2 T has size at most 2| + +X]. We now prove that T is an NCTM for B. Consider the pair [uu] and N(v) for any two distinct vertices u, U E VG).. If u, 0 E I, then T is non-clashing for Nuu] and [N]] as y E [(N for all y E L. If u E X and E I, then T is non-clashing for N [u] and N(v] since if Nuu # Muj. then either V E T(N(u]) or some vertex in X distinguishes N and N(e). some vertex in (u) n
{u}) distinguishes them. Lastly, if u, E X and Niu * No.. then some vertex in X is only in one of N(u) and Nlu] and/or there exists an equivalence class& S of I such that all of S is in N(u] or N(e] and none of S is in the other. In the first case, T's is non-clashing for N [u] and Nyu as X T(N [x] for all x E X. In the second case, T is non-clashing for N Mu) and N as {81,-...8p 8p] T(N for all E X.
A.7 PROOF OF LEMMA 9
Proof. First, we prove that, for any NCTM T of size k for B, if there exist g distinct indices E
[$]
such that up E (u.)). then there exist distinct j.j E [E]] such that un E T(N[u.), uj e
T(N D.
= [(N( XX, [(N[u]) n (Q [u4 } = 0 if and only if T(Nu,))
(Q) (u)) = 0, and (w.)) ns 0 if and only if T(N (N)))) ns = 0 for any equivalence
class& S * Q of T with respect to X. So, assume that there exist q distinct indices p E [e] such that
Up E [(N(u.)). Since there are at most x| equivalence classes of with respect to X, there are at
most 22 distinct subsets of these equivalence classes. Hence, there are at most |||*|+| distinct subsets of X and the equivalence classes. Thus, the existence of and uj with the above properties follows by the pigeonhole principle since = 22 + > x
It remains to prove that, for any NCMT T of size i for B, if > q 4 2k: then there exist q distinct indices p E [e] such that up E [(N(u)) Toward a contradiction, let T be an NCTM of size k for B, let l > q + 2k: and suppose there are most q- distinct indices p [f] such that u, E TNN [up))- For all i E [4]. if u, $ T(N then each of the at most k vertices in T(N distinguishes N [u.] and at most one other closed neighborhood in (N. Nue)]. Thus, w.l.o.g.. for all i E [g 1). let E T(N[u,). By the above analysis, the teaching sets of N Nuul..... N[[]....[[[]) N(ud combined distinguish at most (E (---+11 1)k pairs in {N [ugl..... Muell. Note that (f 1)) 9)/2 such pairs must be distinguished and
(e (L-q +- (E f)/2 > (f - q + 1)k- + (L-1)/2> k = l> 9 2h.
Thus, since l >> q + 2h: T does not distinguish pair in (N(ug):-.. Nuul], contradiction.
A.8 PROOF OF LEMMA
Proof. Let T be an NCTM of size at most & for B. For all w E V(G)) \ {0) such that E T(N [w]), remove u from [w][,)), and if u & T(N[w]), then add u to T(N [w]). From the proof that Reduc- tion rule is safe (Lemma 10 it is easy to see that this maintains that T is an NCTM of size at most for B since Níu and N o are not in B. The reverse direction is trivial since any NCTM for B in G' is also an NCTM for B in G as M(u and [(v) are not in B.
18

---

Published as a conference paper at ICLR 2026
A.9 PROOF OF THEOREM B
Proof. We construct an NCTM 7 of size at most 5 for B. For all e E V(G), if d(o) S 4, then set
T(N()) Nlu]. Otherwise, for each
V(G) with d(v) 5, place any 3 neighbors of v in T( Consider any one such vertex v and let v1, 22 03 be its 3 neighbors in T(N [e]). Then,
as in the proof of Theorem 12 there
most one other vertex u V such that vi, Ug 2g N (u), and hence. I'' satisfies the non-clashee non-clashing condition for N N and Mæa for all a E V(G)
{u. u, 01, 02, Ut } if u exists, and for all x E V(G) {u, 01, 12, 13) otherwise. If u & N then add u to T(N T(N and note that this ensures that T satisfies the non-clashing condition for N [t) and
M[2] for all a E ((G) \ {v} since u & N [... but u N [Mi]. u E N and N [ua]. Hence, in what follows, if exists, then assume that E [(e].
As long as there exists a pair [[v), N y E such that d(v) 2 5, N(u) o Nwy, and T does not currently satisfy the non-clashing condition for the pair, then there exists (Nyl \ N Nlul) that will be added to [(N(u)) or [(] to distinguish the pair. Specifically, [ul \ [N [y]. then add case, T then satisfies the non-clashing condition for N(u] and N(y). Once this process is completed, T is an NCTM for B as it is non-clashing for N(u] and N(v] for any vertex with d(v) 2 5, but also for the closed neighborhoods of any two vertices of degree at most 4 since their teaching sets coincide with their closed neighborhoods in this case. We now argue that there were at most 2 possibilities for above. The vertices in {u, D, 11. 22 U3} cannot form K₃ since G is planar. Thus, one of the edges V1 03 and 22 is not E(G) since 1203 & F(G). Then, could only have been or u1. Hence, at most 2 vertices were added to any teaching set during the above process, and thus, T has size at most 5.
(N[e) \ [wll U
[N [N[o)) and otherwise, add N [y] [[] to T(N [y]). In either
E(G). Say, w.l.o.g., that
19


Reviews:
[{"review_id": "mihYW4uK01", "reviewer": "Reviewer_BjtC", "summary": "The paper studies non-clashing teaching paradigm in learning theory where a teacher can give the learner catered examples instead of random samples in a non-collusive way. Specifically, the authors look at the specific cases where the concept class comes from a closed neighborhood of a graph and provide many theoretical analyses of both upper and lower bounds for this particular problem (which is as general is binary concept class learning).", "questions": "n/a", "limitations": "", "rating": 4, "confidence": 3, "soundness": 3, "presentation": 1, "contribution": 3, "strengths": "The theoretical contribution is significant, as far as the reviewer can tell studying the immediate literature. And the math is correct, as far as the reviewer has checked (barring cited results). While the reviewer is not an expert in the immediate literature and cannot speak to how challenging it is to obtain such results, it is fair to say that the results are novel and comprehensive (spanning many different question, mostly solved to completion).", "weaknesses": "The paper is densely written and assumes some prior knowledge of the literature from the get-go (for instance, the jump from concept classes from balls in graphs in the introduction is a bit too sudden without explaining how a set of balls in G form a binary concept class, especially when graph quantities starts appearing in the bounds (e.g. line 67)). \n\nWhile this is expected from a theoretical paper, especially one that studies a rather niche problem, for the purpose of a machine learning conference, it is highly recommended that the authors defer more full proofs to the appendix, replacing it with a sketch proof, and use the extra space to motivate the relevance of the problem to the machine learning community (e.g. Line 108-114 can benefit from some illustration). A summary such as Table 1 is also something that should be in the main paper, at least the parts that are most significant. \n\nMost of the proofs can use simple illustrations and better guidance (e.g. Theorem 2, Lemma 6, Lemma 10) because of how dense the notations and case analysis is. \n\nIn summary, the theoretical results are interesting and comprehensive, but the presentation of the paper needs major overhaul to be readable. I am willing to give another read and revise the score if the authors can clean up their expositions in the rebuttal period.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "TotasWfXq7", "reviewer": "Reviewer_othc", "summary": "This paper studies the notion of the *non-clashing teaching dimension* (NCTD) within the broader framework of machine teaching, focusing on both variants of non-clashing teaching for *balls in simple finite graphs with closed neighborhoods*.  \nRelying on the Exponential Time Hypothesis (ETH), the authors employ 3-SAT style reductions to establish hardness results and improve algorithmic bounds for the positive variant (**N-NCTD⁺**), while also providing a corresponding lower bound for **N-NCTD**.  \nThey further design a fixed-parameter tractable (FPT) algorithm parameterized by *treedepth* for computing **N-NCTD⁺**, achieved via a pruning mechanism on the treedepth decomposition followed by a brute-force step that is fixed-parameter tractable in the treedepth parameter.  \nAdditionally, they propose a set of safe reduction rules that yield an FPT algorithm parameterized by the *vertex cover number*.  \nThe paper concludes with combinatorial arguments proving constant upper bounds on **N-NCTD⁺** for planar graphs with closed neighborhoods.", "questions": "### Practical Applications and Discussion\n\nCan you list down the practical applications of these notions and improvements?  \nFor **NCTD⁺**, how is it useful to use **treedepth** as compared to **vertex integrity** and what are the tangible benefits, in terms of theory and implementation perspectives?  \nSimilar to **NCTD**, would it be beneficial to have **vertex cover** as it is very general and has good approximation bounds?  \nCan there be some practical experiments to quantify the impacts of **reduction rules** for FPT algorithms for **NCTD** and **NCTD⁺**?", "limitations": "", "rating": 4, "confidence": 3, "soundness": 4, "presentation": 3, "contribution": 2, "strengths": "### Strengths\n\nThe lower bound improvement for **N-NCTD** is significant, and the **FPT parameterization by vertex cover** for **N-NCTD** is highly relevant.  \n\nI found the presentation style particularly effective, as several proofs are preceded by intuitive explanations and supported by neat, well-designed diagrams. This approach makes the paper engaging and easy to follow. I believe this style should be extended to other proofs as well, with additional illustrative examples where appropriate. For example, while showing the correctness of the reduction in **Theorem 2**, since the size of the **NCTM** is 1, an explicit map could be shown to help readers follow the proof without compromising generality.  \n\nI also appreciated the **combinatorial proofs for planar graphs**, which present a large use case and offer elegant solutions. However, the explanation could be made more verbose for better clarity. For instance, in the case where *d(v) ≥ 7*, it would help to explain why there are only four possibilities. A short intuitive note could clarify that this clashing arises only when all three choices match, or due to earlier shifting where two old and one new match occur—such combinations being \\( \\binom{3}{3} + \\binom{3}{2} = 4 \\). Including such brief intuitive explanations would greatly improve readability and pedagogical value.", "weaknesses": "### Weaknesses\n\nThe proofs and overall write-up are very specific and may primarily appeal to readers from the learning theory subcommunity. The paper is difficult to parse and, more importantly, to appreciate for readers without prior background in machine teaching or the concept of the non-clashing teaching dimension (NCTD).  \n\nAlthough the proofs presented in Section 2 appear to be correct and I verified all of them rigorously, I found the graph construction to be very similar to the one used in *“The Computational Complexity of Positive Non-Clashing Teaching in Graphs.”* While correctness is not in question, I believe it is important for proofs to introduce novel ideas or techniques that could be applicable in other contexts; I did not find such novelty in the proofs of this paper.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "aOdehDwXNe", "reviewer": "Reviewer_HDoS", "summary": "This work studies (positive) non-clashing teaching for closed neighborhoods, showing this concept class is broadly representative and yielding stronger ETH-based lower bounds and tighter algorithms than prior results for balls in graphs. It proves no $2^{o(f(k)·|V|)}$ algorithm for N-NCTD under ETH and gives a tight $2^{O(|E|)}$ algorithm with matching lower bound for N-NCTD+, nearly matching known upper bounds in the general case. It further shows FPT results under treedepth (positive variant) and vertex cover (general variant) and derives small combinatorial upper bounds for planar and unit-square graphs, clarifying when structure enables efficient teaching maps.", "questions": "1. Are constructive or approximate teaching strategies possible for additional graph families ?\n2. What are realistic constants in the FPT algorithms and prospects for practical solvers?\n3. A concise taxonomy contrasting closed neighborhoods vs.\\ balls would be valuable.", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. Near-tight complexity results, improving lower bounds and adding new FPT regimes.\n2. Careful comparison to balls in graphs, showing where closed neighborhoods help.\n3. Combinatorial upper bounds tied to structural classes and VC-dimension observations.", "weaknesses": "1. Exposition can be heavy; more intuition and illustrative examples would aid accessibility.\n2. Limited discussion of practical or empirical implications for machine teaching applications.\n3. ETH tightness is strong theoretically, but could be complemented by empirical hardness studies.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "Rd1qIZTrlb", "reviewer": "Reviewer_G64H", "summary": "This paper considers computational complexity aspects of a generalization of the Non-Clashing Teaching Dimension (NCTD) of concept classes. The basic definition of the NCTD, introduced and analyzed in previous works, is as follows. There is a finite binary concept class $C$ and a (computationally powerful) teacher $T$. The teacher maps each $C$ to a set of labeled examples $T(C)$ representing $C$. The constraint is that for each $C \\neq C'$, we should have an example in $T(C) \\cup T(C')$ that is consistent with only one of the concepts. There is also a version NCTD+ that only allows positive labels.\n\nIt turns out that the concept of NCTD can be equivalently represented using balls in graphs. The current work focuses on a more specific case, where the balls are only of radius 1 (\"closed neighborhood\"). The authors prove a range of theoretical results, including an improved exponential conditional hardness (lower bound assuming ETH holds); near-matching upper bounds; Fixed Parameter Tractable upper bounds, parameterized by the tree-depth (among others); and NCTD upper bounds for specific graph classes, such as planar graphs.", "questions": "I do not fully understand what is the connection between the result and the original definition of NCTD (for balls). While I understand that the problems are connected, I do not understand what exactly your results imply. Do they have interesting applications?\n\nDo results for restricted graph classes have, e.g., graphs with low tree depth or planar graphs, have interesting applications? What is the typical structure of graphs in this setting?", "limitations": "", "rating": 4, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "- Strong theoretical results which extend the state of the art understanding of problems related to machine teaching.\n\n- The proofs are interesting and well-written. I did not fully verify, but the main arguments seem believable.", "weaknesses": "- It is not clear what are the applications of the results, and how they relate to learning. If such applications exist, the author should make a better effort clarifying these.\n\n- The paper is purely theoretical and might not be a best fit to a conference like ICLR. While the results seem interesting (even without concrete applications), they are probably a better fit in a more theoretical venue.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (Poster)