The Computational Complexity of Positive Non-Clashing Teaching in Graphs

The Computational Complexity of Positive Non-Clashing Teaching in Graphs* Robert Ganiana, Liana Khazaliyaa, Fionn Mc Inerneyb, and Mathis Roctona aAlgorithms and Complexity Group, TU Wien, Austria bTelef´ onica Scientific Research, Barcelona, Spain Abstract 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 fixedparameter 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. 1 Introduction While typical machine learning models task a learner with finding a concept Cfrom a concept class Cbased on an—often randomly drawn—sample, in machine teaching (specifically in its commonly considered batch variant) the learner is provided a set of examples by a teacher; crucially, here the examples can be selected in a way which allows the concept to be reconstructed from as few examples as possible. Machine teaching is a core topic in computational learning theory and has found applications in a variety of areas including robotics [TC09, ACYT12], trustworthy AI [MZ15, ZZW18], inverse reinforcement learning [HLM+16, BN19], and education [Zhu15, CSM+18, ZSZR18]. While numerous models of machine teaching have been investigated to date [SM91, GK95, GM96, ZLHZ11, GRSZ17, MCV+19, THF19], in this article we focus on the recently developed positive non-clashing teaching model [KSZ19, FKS+23]. In non-clashing teaching, given a finite binary concept class C, for each pair C1,C2of distinct concepts in C, at least one example provided for at least one of C1or C2must not be consistent with the other concept. A key feature of non-clashing teaching is that it is the most efficient model (in terms of the number of required examples) satisfying the Goldman-Mathias collusion-avoidance criterion [GM96]—the “gold standard” for ensuring that the learner cannot cheat, e.g., via a hidden communication channel with the teacher. Moreover, a teaching model is positive if the examples provided for each concept Care required to be positively labeled for C. The restriction of teaching models to the positive setting is common and well-motivated from applications in, e.g., recommendation systems [SPK00], computational biology [WDMH06, YJSS08], and grammatical inference [SO94, Den01]; see also the early works of Angluin [Ang80b, Ang80a]. Non-clashing teaching has been proposed and studied in the positive setting not only within the initial papers introducing the concept [KSZ19, FKS+23], but also in subsequent works (e.g., [CCMR24]). While positive non-clashing teaching has the potential to be highly efficient, realizing this potential requires us to solve the computational task of actually constructing a small set of examples for the given concepts. More precisely, *An extended abstract of this paper will appear in the proceedings of ICLR 2025. 1 one aims at computing (a witness for) the teaching dimension of a given concept class, i.e., the minimum integer k such that each concept is provided with at most kexamples that satisfy the conditions of the model. On the positive side, instead of considering various different types of concepts and examples, we can restrict our attention to the setting where each concept is a ball in some input-specified graph G, and the possible examples are vertices of G. Indeed, it is known that any finite binary concept class C ⊆ 2Vcan be represented by a set Bof balls in a graph Gas follows: V(G) = V∪{xC|C∈ C},xCis adjacent to xC′for all C, C′∈ C,xCis adjacent to v∈Vif and only if v∈C, and B={B1(xC)|C∈ C}[CCM+23, CCMR24]. On the negative side, the problem is computationally intractable, and remains so even in the restricted setting where every possible concept (i.e., every ball in G) is present; to distinguish this case from the general one where not all concepts need to be present, we refer to it as strict. In particular, Chalopin, Chepoi, Mc Inerney, and Ratel [CCMR24] recently carried out an initial complexity-theoretic investigation of computing the positive non-clashing teaching dimension in the strict setting. There, they established the NP-hardness of the problem for instances with large teaching dimension (even when restricted to the highly restricted class of split graphs), obtained runtime upper and lower bounds under the Exponential Time Hypothesis [IPZ01], and designed a so-called fixed-parameter algorithm for the problem when parameterized by the size of the vertex cover of G. In this article, we significantly improve over each of these results, answer two open questions posed by the authors of the aforementioned work [CCMR24], and obtain a nearly complete understanding of the computational complexity of computing the positive non-clashing teaching dimension (in both the strict and non-strict settings). Contributions. Let us refer to the problems of computing the positive non-clashing teaching dimension in the strict and non-strict settings as STRICT NON-CLASH and NON-CLASH, respectively. Formal definitions complementing the informal descriptions given above are provided in Section 2. Our first result concerns the complexity of STRICT NON-CLASH on instances with constant positive non-clashing teaching dimension. The reductions of Chalopin, Chepoi, Mc Inerney, and Ratel [CCMR24] only establish the NPhardness of the problem for instances with large (i.e., input-dependent) positive non-clashing teaching dimension k. In fact, as their first open question, the authors ask whether STRICT NON-CLASH is NP-hard or polynomial-time solvable when the sought-after dimension kis a fixed constant; the question is not only theoretically interesting, but also highly relevant as instances of small teaching dimension are precisely the candidates for efficient teaching. We settle this by a highly non-trivial reduction (Theorem 1) which establishes that determining whether the positive non-clashing teaching dimension is at most 2is NP-hard—and remains so even when restricted to the same class of split graphs where STRICT NON-CLASH was previously shown to be NP-hard (for large k) [CCMR24]. We note that this result is, in a sense, best possible: determining whether an instance of STRICT NON-CLASH has a positive non-clashing teaching dimension of 1is trivial as it is equivalent to testing whether Gis edgeless [CCMR24]. Next, we proceed to the running time bounds for solving the problem. Typically, the running time upper bounds are given by an exact algorithm, while the lower bounds are obtained from a suitable “tight” reduction under the Exponential Time Hypothesis [IPZ01]. In the preceding work, Chalopin, Chepoi, Mc Inerney, and Ratel [CCMR24] obtained algorithmic lower and upper bounds of 2o(n·d)and 2O(n2·d), where nand dare the number of vertices and the diameter of G, respectively. From our reduction and a more careful algorithmic analysis, we obtain a lower bound of 2o(n·d·k)and an upper bound of 2O(n·d·k·log n)(Theorem 4 and Proposition 5)—making the bounds almost tight, with just a logarithmic factor in the exponent separating the two. While the aforementioned bounds apply to the problem in general, often one may only need to solve the problem on “well-structured” graphs. The more refined parameterized complexity paradigm [DF13, CFK+15] offers the perfect tools to analyze and identify precisely which structural properties of input graphs—usually captured by a suitable integer parameter k—allow us to circumvent its general intractability. The analog to the complexity class Pin the parameterized setting is FPT (“fixed-parameter tractable”), which characterizes parameterized problems solvable in f(k)·nO(1) time; intuitively, this means that the problem is solvable in uniformly polynomial time for each constant value of k. Parameterized complexity is well-established and has been successfully applied for non-clashing teaching [CCMR24] as well as in a variety of related subfields of learning theory [DEF93, LL18, GK21, OS21, BGS23, EGK+23, EOPS23]. In their previous work, Chalopin, Chepoi, Mc Inerney, and Ratel [CCMR24] established the fixed-parameter tractability of STRICT NON-CLASH when parameterized by the vertex cover number of the input graph G—or, equiva2 lently, the vertex deletion distance to a graph consisting only of isolated vertices. The drawback of that result is that the vertex cover number is a highly “restrictive” parameter, in the sense that it achieves low values only on rather simple graphs. This is also reflected in the open question posed in that article, which asked about the problem’s complexity under other parameterizations. As our third contribution, we establish (in Theorem 18) the fixed-parameter tractability of NON-CLASH—i.e., the more general task of computing the non-clashing teaching dimension when not all concepts (i.e., balls) need to be present—parameterized by the vertex integrity of G. Vertex integrity is a well-studied graph parameter [DDvtH16, GHK+22, GO24, HLVY24] that essentially captures the vertex deletion distance to a graph consisting only of small connected components; it is known (and easily observed) to be a less restrictive parameterization than the vertex cover number (cf. Section 2), meaning that our result significantly pushes the boundaries of tractability even for the simpler strict variant of the problem. The proof of Theorem 18 is highly non-trivial. In particular, while the algorithm itself is simple and merely uses a data reduction technique (“kernelization” [CFK+15]) that iteratively removes certain parts of the instance, the crucial correctness proof underlying the result is very involved and relies on identifying a carefully defined set of “canonical” examples for our instances. The algorithm is also constructive, meaning that it can output a set of examples for the concepts as a witness. As our final contribution, in Theorem 19 we complement Theorem 18 with a complexity-theoretic lower bound excluding fixed-parameter tractability under many other graph parameters previously considered in the literature, including pathwidth,treewidth, and the feedback vertex number—the latter two of which were explicitly mentioned in the aforementioned open question [CCMR24]. We do so through a complex W[1]-hardness reduction (which can be seen as a parameterized analog to classical reductions used to establish NP-hardness) that excludes, under wellestablished complexity assumptions, NON-CLASH from being in FPT even when combining all the parameterizations mentioned in the previous sentence with the positive non-clashing teaching dimension k. Related Work. It is known that NON-CLASH is significantly more challenging than the special case captured by STRICT NON-CLASH. For instance, the reduction of Kirkpatrick, Simon, and Zilles [KSZ19, Subsection 7.1] establishes that NON-CLASH is NP-hard even if the task is to determine whether the positive non-clashing teaching dimension of the instance is 1; on the other hand, the analogous question for STRICT NON-CLASH is trivial as it simply requires determining whether the input graph is edgeless or not [CCMR24]. In fact, unless P=NP, that reduction also rules out a polynomial-time 1.999-approximation algorithm. For clarity, note that while that reduction does not consider concepts that are balls in a graph, as mentioned earlier, every finite binary concept class can be easily transformed into a class of balls in a graph [CCM+23, CCMR24]. Apart from the computational questions resolved in this work, another prominent open question is whether the nonclashing teaching dimension is upper-bounded by the VC-dimension [KSZ19, FKS+23, Sim23]. It is known that the non-clashing teaching dimension (where one allows negative examples) can be significantly smaller than the positive variant, e.g., balls in cycles have a non-clashing teaching dimension of 2, but their positive non-clashing teaching dimension is not bounded by any constant [CCMR24]. It was also pointed out that balls in cacti or planar graphs could be good candidates for concept classes negatively answering this question [CCMR24]. Further, Simon [Sim23] recently explored the relationship between non-clashing teaching and recursive teaching and identified the precise gap between the two notions. Concept classes consisting of balls in a graph are a discrete analog of the geometric concept classes of balls in a Euclidean space which have been investigated in PAC-learning, e.g., as part of the more general Dudley concept classes [Flo89, BDL98]. Apart from non-clashing teaching, they have also been explored for the closely related and well-studied sample compression schemes [CCM+23] introduced by Littlestone and Warmuth [LW86]. As discussed in prior works [KSZ19, FKS+23, CCMR24], non-clashing teaching maps can be viewed as signed variants of representation maps for concept classes, a notion introduced to design unlabeled sample compression schemes for maximum concept classes [KW07] (and subsequently the more general ample concept classes [CCMW22]). 2 Preliminaries We assume familiarity with graph terminology [Die24]. We only consider simple, finite, and undirected graphs. For an integer n≥1, we set [n] := {1, . . . , n}. As we only consider finite binary concept classes which can be represented 3 as balls in graphs [CCM+23, CCMR24], we introduce the terminology for positive non-clashing teaching directly in the setting of graphs. Positive Non-Clashing Teaching in Graphs. Let Gbe a graph. For an integer r≥0and a vertex v∈V(G), the ball Br(v)is the set of all vertices at distance at most rfrom its center v. Let Bbe a set of balls of G. A positive teaching map Tfor Bis a mapping which assigns to each ball B∈ B ateaching set T(B)⊆B,i.e., a subset of the vertices of B. The dimension of Tis maxB∈B |T(B)|—in other words, the largest image of T. A positive teaching map Tis called non-clashing for Bif for each pair of distinct balls B1, B2∈ B, there exists a vertex w∈T(B1)∪T(B2)such that w∈ B1∩B2. Note that wmust lie in B1∪B2by definition, and hence, this condition ensures that one of the balls has a teaching set which is not contained in the other ball. We say that wdistinguishes B1and B2, or distinguishes B1from B2(or vice versa). If a teaching map is not non-clashing, we say that there is aconflict between any two balls for which there is no element distinguishing them. We now define our problems of interest:1 STRICT NON-CLASH Input: A graph Gand an integer k. Question: Is there a positive non-clashing teaching map for the set of all balls of Gwith dimension at most k? NON-CLASH Input: A graph G, a set Bof balls of G, and an integer k. Question: Is there a positive non-clashing teaching map for Bwith dimension at most k? We call a teaching map satisfying the conditions of the respective problem statement a solution. To avoid any confusion, we remark that the above definitions—as well as every result obtained in this article—concerns non-clashing teaching in the previously studied positive setting. Parameterized Complexity. In parameterized complexity [DF13, CFK+15], the running-times of algorithms are studied with respect to a parameter p∈Nand input size n. It is normally used for NP-hard problems, with the aim of finding a parameter describing a feature of the instance such that the combinatorial explosion is confined to this parameter. A parameterized problem is fixed-parameter tractable (FPT) if it can be solved by an algorithm running in time f(p)·nO(1), where fis a computable function; these are fixed-parameter algorithms. Proving that a problem is W[1]-hard via a parameterized reduction from a W[1]-hard problem Prules out the existence of a fixed-parameter algorithm under the well-established hypothesis that W[1] =FPT. A parameterized reduction from Pto a parameterized problem Qis a function: • which maps YES-instances to YES-instances and NO-instances to NO-instances, • is computable in time f(p)·nO(1), where fis a computable function, and • where the parameter of the output instance can be upper-bounded by some function of the parameter of the input instance. STRICT NON-CLASH is known to be fixed-parameter tractable when parameterized by the vertex cover number of G,i.e., the minimum integer asuch that there is a subset X⊂V(G)of at most avertices where G−Xis an edgeless graph. In this article, we consider three parameters which are upper-bounded by the vertex cover number (or, more precisely, the vertex cover number plus one): • the vertex integrity of G, which is the minimum integer bsuch that there is a vertex subset X⊂V(G)where for every connected component Hof G−X,|V(H)∪X| ≤ b; • the feedback vertex number of G(denoted by fvs(G)), which is the minimum integer csuch that there is a vertex subset X⊂V(G)where G−Xis acyclic; 1While we use decision variants, our algorithms are constructive and can output a teaching map as a witness. 4 • the pathwidth of G(denoted by pw(G)), which has a more involved definition based on the notion of path decompositions. However, for the purposes of this article it is sufficient to note the well-known facts [DF13, CFK+15] that deleting one vertex from each connected component of Gwill decrease the pathwidth by at most one, and that a graph consisting of a disjoint union of paths and subdivided caterpillars (i.e., graphs consisting of a central path with pendent paths attached to it) has pathwidth 2. 3 Intractability and Running Time Lower Bounds In this section, we establish the NP-hardness of STRICT NON-CLASH when k= 2, and thus, that it cannot be 1.499approximated in polynomial time unless P=NP; in fact, our results hold even when the graphs belong to the class of split graphs,i.e., graphs which can be partitioned into an independent set and a clique. Recall that the former result is tight in the sense that STRICT NON-CLASH is trivial when k= 1 [CCMR24]. We formalize the result below. Theorem 1. STRICT NON-CLASH is NP-hard even when restricted to split graphs with k= 2. We prove Theorem 1 via a polynomial-time reduction that, given an instance of 3-SAT, constructs an equivalent instance (G, k)of STRICT NON-CLASH, where Gis a split graph and k= 2. 3-SAT Input: A CNF formula over a set of clauses C={c1, . . . , cm}containing variables from X={x1, . . . , xn}, where each clause has exactly 3literals. Question: Is there a variable assignment τ:X → {True,False}satisfying each clause in C? Reduction. Given an instance ϕ= (C,X)of 3-SAT, we construct the graph Gas follows (see Figure 1b for an illustration). • First, for each i∈[n], we create a pair of vertices {ti, fi}. We set A:= {ti, fi}i∈[n]. • For each i∈[n], we introduce a variable force-gadget, which consists of a set of vertices {r∗ i, r∗∗ i, r∗∗∗ i, r′ i, r′′ i} and edges as depicted in Figure 1a. • For each i∈[n], we attach the variable force-gadget to the pair {ti, fi}as shown in Figure 1b, by making both r∗ iand r∗∗∗ iadjacent to both tiand fi. This gadget will guarantee that the corresponding assignment of the ith variable is well-defined. We set R∗:= {r∗ i, r∗∗ i, r∗∗∗ i}i∈[n]and R′:= {r′ 0}∪{r′ i, r′′ i}i∈[n], where r′ 0is a new vertex. • Similarly, for each k∈[m], we introduce a clause force-gadget on the set of new vertices {s∗ k, s∗∗ k, s∗∗∗ k, s′ k, s′′ k} (as depicted in Figure 1a). This gadget corresponds to the clause ckof the instance ϕ. We add adjacencies according to the appearance of literals in ck,i.e., if xi∈ckfor some i∈[n], then we connect both s∗ kand s∗∗∗ k to fi; and if xi∈ck, then we connect both s∗ kand s∗∗∗ jto ti. Intuitively, we connect the gadget to those vertices whose underlying assignments (True or False for tiand fi, resp.) do not satisfy ck, while the opposite assignments would (see Figure 1b). We set S∗:= {s∗ k, s∗∗ k, s∗∗∗ k}k∈[m]and S′:= {s′ 0}∪{s′ k, s′′ k}k∈[m], where s′ 0is a new vertex. • We add all possible edges between (a) S∗and R∗; (b) R∗and S′; (c) S∗and R′. • We add all possible edges within S∗, and within R∗. • Lastly, we add a special vertex aand make it adjacent to all the other vertices of the graph. This concludes the construction of G; given an instance ϕ= (C,X)of 3-SAT, the reduction outputs the STRICT NON-CLASH instance (G, 2). We now prove its correctness via the next two lemmas. Lemma 2. If ϕis a YES-instance of 3-SAT, then (G, 2) is a YES-instance of STRICT NON-CLASH. 5 v′ v′′ v∗ v∗∗ v∗∗∗ (a) The force-gadget. The dotted edge corresponds to the absence of that edge. s′ k s′′ k s∗ k s∗∗ k s∗∗∗ k s′ l s′′ l s∗ l s∗∗ l s∗∗∗ l r′ i r′′ i r∗ i r∗∗ i r∗∗∗ i r′ j r′′ j r∗ j r∗∗ j r∗∗∗ j r′ q r′′ q r∗ q r∗∗ q r∗∗∗ q r′ p r′′ p r∗ p r∗∗ p r∗∗∗ p ti fi tj fj tq fq tp fp s′ 0 r′ 0 S′ R′ A S∗ R∗ a (b) An example of the graph Gobtained by applying our reduction on the 3-SAT instance with X={xi, xj, xq, xp}and C={(xi∨xj∨xq),(xj∨xq∨xp)}. Vertices in ovals form independent sets, while cliques are depicted by rectangles. Blue edges denote the existence of all possible edges between the two sets. Proof. As Gcontains a universal vertex a, its diameter is 2, and thus, any ball of radius at least 2contains V(G). Hence, it is sufficient to consider balls of radius at most 2. Let τ:X → {True,False}be an assignment of the variables satisfying the given 3-SAT formula ϕ. Let us define a positive teaching map Tof dimension 2for the set B of all the balls in Gas shown in Table 1. It remains to prove that Tis non-clashing for B. To this end, we will refer to Table 2 which intuitively describes which vertices are used to distinguish each pair of balls of radius 1. For any pair u, z ∈V(G), the corresponding entry in the table contains either vor a given vertex w∈V(G). If it contains a vertex w∈V(G), observe that w∈T(B1(u)) ∪T(B1(z)) by Table 1, and w /∈B1(u)∩B1(z). In the remaining cases, i.e.,(1) s∗ k, r∗ i;(2) s∗ k, s∗∗ k;(3) s∗ k, s′ k;(4) s∗ k, s′′ k, we need to make it explicit which vertex vstands for. For pairs (2) s∗ k, s∗∗ k;(3) s∗ k, s′ k;(4) s∗ k, s′′ k,vcan be any vertex in N(s∗ k)∩A(by construction, there are 3such vertices) since the neighborhoods of each of s∗∗ k,s′ k, and s′′ kdo not intersect A. For the last type of pair (1), we will use the fact that τis a satisfying assignment. For k∈[m]and i∈[n], assume w.l.o.g. that ckis satisfied by the assignment τ(xi) = True. Then, T(B1(s∗ k)) = {s′ k, fi}and T(B1(r∗ i)) = {r′ i, ti}. With such an assignment of teaching sets, for any pair of type s∗ k, r∗ iwe have that ti∈T(B1(s∗ k)) ∪T(B1(r∗ i)) = {s′ k, fi}∪{r′ i, ti}, and ti/∈B1(s∗ k)∩B1(r∗ i). Finally, we check that the teaching set for T(V(G)) distinguishes V(G)from all the other balls in G. According to Table 1, for i, j ∈[n]and i=j,T(V(G)) = {ti, tj}and there is no k∈[m]such that both xiand xjappear in ck. The last condition guarantees us that, for any u∈V(G)\{a}, there is a vertex (either tior tj) that is in T(V(G)) but not in B1(u)as there is no clause force-gadget that would be attached to both tiand tj. Thus, we showed that for any pair of balls in B, both necessary conditions for the defined teaching sets hold. Hence, the defined positive teaching map is non-clashing for B. Lemma 3. If (G, 2) is a YES-instance of STRICT NON-CLASH, then ϕis a YES-instance of 3-SAT. 6 for k∈[m]T(B1(s∗ k)) = {s′ k, v}and ckis satisfied by τ(xi)for some i∈[n], where if τ(xi) = True, then v=fi(fi∈B1(s∗ k)∩Asince xi∈ck) if τ(xi) = False, then v=ti(ti∈B1(s∗ k)∩Asince xi∈ck) T(B1(s∗∗ k)) = {s′ k, r′ 0}T(B1(s∗∗∗ k)) = {s′′ k, r′ 0} T(B1(s′ k)) = {s′ k, s∗∗ k}T(B1(s′′ k)) = {s′′ k, s∗∗∗ k}T(B1(s′ 0)) = {s′ 0, a} for i∈[n]T(B1(r∗ i)) = {r′ i, v}, where if τ(xi) = True, then v=ti if τ(fi) = False, then v=fi T(B1(r∗∗ i)) = {r′ i, s′ 0}T(B1(r∗∗∗ i)) = {r′′ i, s′ 0} T(B1(r′ i)) = {r′ i, r∗∗ i}T(B1(r′′ i)) = {r′′ i, r∗∗∗ i}T(B1(r′ 0)) = {r′ 0, a} for i∈[n]T(B1(ti)) = {ti, a}T(B1(fi)) = {fi, a} T(V(G)) = T(B1(a)) = {ti, tj}, for i, j ∈[n],i=jsuch that there is no k∈[m]where both xiand xjappear in ck.a Table 1: Positive teaching map for B. aWe can assume the existence of such a pair i, j, because introducing an artificial variable and a unique clause in which it occurs gives an equivalent instance. Indeed, the artificial variable appears only once and its assignment can be chosen so that the added clause is satisfied without the rest of the formula being affected. Proof. Let Tbe a positive non-clashing teaching map of dimension 2for the set Bof all balls in G. By definition, for each pair of distinct balls B1, B2∈ B, there is w∈T(B1)∪T(B2)such that w /∈B1∩B2. For each i∈[n], consider a pair of vertices r∗ iand r∗∗∗ i. By the construction, B1(r∗∗∗ i)⊂B1(r∗ i)and r′ iis the unique vertex in B1(r∗ i) that is not in B1(r∗∗∗ i)∩B1(r∗ i). Thus, since Tis a positive non-clashing teaching map for B,r′ iis in T(B1(r∗ i)). Now, consider a pair of vertices r∗ iand r∗∗ i. Similarly, B1(r∗∗ i)⊂B1(r∗ i)and {ti, fi}=B1(r∗ i)\B1(r∗∗ i). So, for T to distinguish B1(r∗∗ i)and B1(r∗ i), exactly one of tiand fi(as T(B1(r∗ i)) already contains r′ i) is in T(B1(r∗ i)). The same arguments work for clause force-gadgets, by symmetry of the construction, and we obtain that, for each k∈[m], there is v∈B1(s∗ k)∩Asuch that T(B1(s∗ k)) = {s′ k, v}. Now, let us use the fact that for i∈[n]and k∈[m], the balls B1(r∗ i)and B1(s∗ k)are distinguished by T. If B1(s∗ k)∩{ti, fi}=∅, whichever of ti,fithat is in B1(r∗ i)distinguishes the two balls. However, as we have shown before, for each k∈[m],|T(B1(s∗ k)) ∩A|= 1. So, there exists i∈[n]such that B1(s∗ k)∩{ti, fi} =∅. W.l.o.g., let us assume that B1(s∗ k)∩ {ti, fi}=fi(which means that T(B1(s∗ k)) = {s′ k, fi}). As a result, the only valid option for B1(r∗ i)to be distinguished from B1(s∗ k)is that T(B1(r∗ i)) = {r′ i, ti}. In the other symmetric case where B1(s∗ k)∩{ti, fi}=ti, we obtain T(B1(r∗ i)) = {r′ i, fi}. Let us now define an assignment τ:X → {True,False}in the following way. For each i∈[n], if ti∈ T(B1(r∗ i)), we set τ(xi) = True; otherwise fi∈T(B1(r∗ i)) and we set τ(xi) = False. Let us show that τ indeed satisfies the 3-SAT instance ϕ. As we discussed above, for each k∈[m],T(B1(s∗ k)) has an intersection with Ain exactly one vertex, w.l.o.g., let it again be that T(B1(s∗ k)) ∩A={fi}. Then, T(B1(r∗ i)) ∩A={ti}. So, τ(xi) = True. By our reduction, s∗ kis adjacent to fiif assigning False to xidoes not satisfy ck, while assigning True to xiwould. Thus, the assignment τsatisfies all the mclauses of the initial 3-SAT instance ϕ. The proof of Theorem 1 then follows from Lemma 2 and Lemma 3. In particular, they prove that there is a polynomial-time reduction which transforms any instance of 3-SAT with nvariables and mclauses into an equivalent instance (G, 2) of STRICT NON-CLASH where |V(G)|=O(n+m)and Gis a split graph of diameter 2. The properties of this reduction also allow us to infer more precise algorithmic lower bounds. In particular, since an algorithm solving STRICT NON-CLASH in 2o(|V(G)|·d·k)time would allow us to solve 3-SAT in 2o(n+m)time: Theorem 4. Unless the Exponential Time Hypothesis fails, there is no algorithm solving STRICT NON-CLASH in time 2o(|V(G)|·d·k), where dand kare the diameter of Gand the target positive non-clashing teaching dimension of the instance, respectively. 7 s∗ ks∗∗ ks∗∗∗ ks′ ks′′ ks′ 0tifi r∗ iv r′ 0r′ 0r′ ir′ ir′ ir′ ir′ i r∗∗ is′ 0r′ 0r′ 0s′ 0s′ 0r′ ir′ ir′ i r∗∗∗ is′ 0r′ 0r′ 0s′ 0s′ 0r′′ ir′′ ir′′ i r′ is′ kr′ 0r′ 0r′ ir′ ir′ ir′ ir′ i r′′ is′ kr′ 0r′ 0r′′ ir′′ ir′′ ir′′ ir′′ i r′ 0s′ ks′ ks′′ ks′ ks′′ kr′ 0r′ 0r′ 0 tjs′ ks′ ks′′ ks′ ks′′ ks′ 0tifi fjs′ ks′ ks′′ ks′ ks′′ ks′ 0tifi (a) Here i, j ∈[n],k∈[m], and v∈ {ti, fi} \ N(s∗ k). According to Table 1, {ti, fi} \ N(s∗ k) = tiif xi=True satisfies ck; and {ti, fi} \ N(s∗ k) = fiif xi=False satisfies ck. s∗ ks∗∗ ks∗∗∗ ks′ ks′′ k s∗ ls′ kv s′ kv v s∗∗ ls′ ks′ ks′ kr′ 0r′ 0 s∗∗∗ ls′ ks′ ks′′ kr′ 0r′ 0 s′ ls′ ks′ ks′′ ks′ ks′ k s′′ ls′ ks′ ks′′ ks′ ks′′ k s′ 0s′ 0s′ 0s′ 0s′ 0s′ 0 (b) Here, k, l ∈[m]; filled cells correspond to the case k=l, and the others to k=l. Here, vis any vertex in N(s∗ l)∩A. The table for vertices of the variable forcegadgets is defined similarly, interchanging all sand rsymbols. Table 2: For each u, z ∈V(G), in a cell at the intersection of the corresponding row and column, we place a vertex w∈V(G)such that w∈T(B1(u)) ∪T(B1(z)) and w /∈B1(u)∪B1(z)(according to the teaching map defined by Table 1). We complement this lower bound with a refined upper bound for the more general NON-CLASH: Proposition 5. NON-CLASH can be solved in 2O(|V(G)|·d·k·log |V(G)|)time. Proof. We can assume that Gis connected, as otherwise we can solve NON-CLASH independently on each of the connected components of G. For any v∈V(G)and r∈N, there are at most |V(G)| k=O(2k·log |V(G)|)possible choices for T(Br(v)), and there are at most O(|V(G)| · d)unique balls in G. Due to the latter, for each possible teaching map, we can check in polynomial time whether it is a positive teaching map that satisfies the non-clashing teaching property. Thus, there is a brute-force algorithm running in 2O(|V(G)|·d·k·log |V(G)|)time. 4 Fixed-Parameter Tractability via Vertex Integrity Given that NON-CLASH is NP-hard, it is natural to ask whether the problem can be solved efficiently on inputs exhibiting some well-defined structural properties. In this section, we establish the fixed-parameter tractability of NON-CLASH when parameterized by the vertex integrity of the input graph. Consider an instance (G, B, k)of NONCLASH and let pbe the vertex integrity of G. As the first step, we invoke the known algorithm to compute a “witness” for the vertex integrity in time pO(p)|V(G)|[FS89], i.e., a set X⊂V(G)such that |V(H)∪X| ≤ pfor each connected component Hof G−X. Let Hdenote the set of connected components of G−X. To make use of the vertex integrity of G, we will partition the components of Hinto a parameter-bounded number of equivalence classes such that the elements belonging to the same class share some structural properties that will allow us to consider them, to some extent, interchangeable. Definition 1. Two subgraphs H, H′∈ H are twin-blocks with respect to B, denoted H∼BH′, if there exists an isomorphism αH,H′from Hto H′with the following properties: •for each u∈V(H)and v∈X,uv ∈E(G)if and only if αH,H′(u)v∈E(G), and •for each u∈V(H)and r∈N,Br(u)∈ B if and only if Br(αH,H′(u)) ∈ B. Intuitively, H∼BH′if and only if there is a bijection αH,H′between the vertices of the two subgraphs which preserves (1) edges inside Hand H′, (2) edges to X, and (3) the existence of balls in Bcentered at the vertices of H 8 and H′. We refer to αH,H′as the canonical isomorphism between the two twin-blocks at hand, and if multiple choices of αexist, we choose and fix one arbitrarily; we drop the indices of αwhen the subgraphs are clear from the context. Observe that for any choice of Hand H′,H∼BH′can be tested in time at most pO(p)by enumerating all possible choices of α. Clearly, ∼Bis an equivalence relation and we denote by [H]∼Bthe equivalence class containing H. For u∈V(H), we further define [u]∼B={αH,H′(u)|H′∈[H]∼B}, and similarly for Br(u)∈ B,[Br(u)]∼B={Br(u′)∈ B|u′∈[u]∼B}; intuitively, these refer to the sets of counterparts of uand Br(u)in the equivalence class, respectively. For brevity, we overload the notation ∼Band use v∼Bw(or Br(v)∼BBr(w)) to express that v∈[w]∼B(or Br(v)∈[Br(w)]∼B, respectively). Observation 6. The number of equivalence classes on Hdefined by ∼Bis at most 2O(p3). Proof. All graphs in Hhave size at most p, which means that the number of non-isomorphic graphs in Hcan be trivially upper-bounded by p·2p2. Since |X|< p, there are also at most p2possible edges between Xand any H∈ H in G. Lastly, the number of balls centered in H∈ H is bounded above by the number of vertices in Htimes the diameter of G, which is p· O(p2) = O(p3). Indeed, the diameter of a connected graph with vertex integrity pis at most O(p2), since the parameter does not increase by taking induced subgraphs and the vertex integrity of a path of length jis O(√j). Combining these elements, we can upper-bound the total number of equivalence classes by p·2p2·2p2·2O(p3)= 2O(p3). While the equivalence relation ∼Bis defined based on the input (in particular, Gand B), our proof requires also considering a more refined equivalence relation based on the structure of a hypothetical positive non-clashing teaching map. Toward this, we use the following notion to capture how a hypothetical teaching set interacts with the balls centered in the components of H. Definition 2. The blueprint Sof a teaching set T(B)for a ball B=Br(u)centered in H∈ His a tuple (SX, SH, Sf) composed of: 1. the set SX=T(B)∩X, 2. the set SH=T(B)∩V(H), 3. the set Sf={fH0|H0∈ H} of functions, where for each H0the function fH0:V(H0)→ {0,1,2}specifies whether for a vertex v∈V(H0), the set ([v]∼B∩T(B)) \V(H)of counterparts of voutside of Hhas size 0, 1or at least 2. Intuitively, the blueprint specifies how the teaching set for Binteracts with (1) the set Xand (2) the vertices inside Hitself; for the rest of the graph, the blueprint also counts how many “equivalent” vertices it contains from each equivalence class of H,but only up to 2. At this point, it may not be clear why we do not differentiate between any size greater than 2; the reason is that if the actual size is 3or more, there are superfluous elements in the teaching set, as we prove below. In fact, we prove a more general statement which holds regardless of whether vertices in Hare counted or not. Lemma 7. Let u∈V(G),B=Br(u)∈ B, and Tbe a positive non-clashing teaching map for B. Suppose there exist H0∈ Hand v∈V(H0)such that |[v]∼B∩T(B)| ≥ 3. Then, there exists zin [v]∼B∩T(B)such that removing zfrom T(B)yields a positive non-clashing teaching map for B. Proof. Let vand H0satisfy the premise, and let z1, z2, z3be three distinct elements of {w∈T(B)|w∈V(H′), H′∼B H0, α(w) = v}. We denote by H1(H2,H3, resp.) the component of Hcontaining z1(z2,z3, resp.). By definition, these components are disjoint since the vertices are ∼B-equivalent, and thus, ucan be in at most one of H1, H2, H3 (and possibly none, i.e.,ucould be in some other component or in X). Without loss of generality, we assume that uis not in V(H3), and claim that removing z3from T(B)results in a positive non-clashing teaching map T′for B. We prove this claim as follows. Toward a contradiction, suppose there is a ball B′=Br′(u′)such that T′does not satisfy the non-clashing condition for Band B′. Then, z3was the only vertex in T(B)∪T(B′)that was not contained in B∩B′, and hence, z3/∈B′and z1, z2∈B′. Therefore, d(u′, z1)< d(u′, z3), which implies that u′∈V(H1) 9 the opposite vertices to Brc(c)in Px,Py, and Pz(whose respective indices correspond to the respective variable values that do not satisfy the clause c), while ensuring that no unwanted shortcuts exist in G. • For each clause c∈ C and each variable q∈ X such that cdoes not contain q, in G, connect the vertices cand c′to q1by distinct paths of length 3d. These paths ensure that the balls Brc(c)and Br′ c′(c′)described above contain every other variable path completely, while ensuring that no unwanted shortcuts exist in G. • Let Sbe the set of all the vertices that currently exist in G. For each x∈ X, in G, make a vertex fxand connect it to each vertex in Sexcept those in Pxvia a distinct path of length 6d. Finally, for all x, y ∈ X, make fx adjacent to fy. This ensures that, for each x∈ X, the ball B6d(fx)contains every vertex in Gexcept for those in Px, while ensuring that no unwanted shortcuts exist in G. This completes the construction of G(see Figure 2). Set k:= |X|. Let Bconsist of V(G),B6d(fx)for all x∈ X, and Brc(c)and Br′ c′(c′)for all c∈ C. Correctness of the Reduction. Suppose, given an instance ϕof NAE-INTEGER-3-SAT, that the reduction from the subsection above returns (G, B, k)as an instance of NON-CLASH. Lemma 20. ϕis a YES-instance of NAE-INTEGER-3-SAT if and only if (G, B, k)is a YES-instance of NON-CLASH. Proof. First, suppose that ϕis a YES-instance of NAE-INTEGER-3-SAT. We construct a positive teaching map Tas follows. In the NAE-satisfying variable assignment for ϕ, for each variable x∈ X, if the integer jis assigned to x, then place xjin T(V(G)). For each c∈ C, set T(Brc(c)) := {c}and T(Br′ c′(c′)) := {c′}. Lastly, for each x∈X, T(B6d(fx)) contains fxand one arbitrary vertex from each of the k−1variable paths it contains. We prove that Tis non-clashing for B. For any two balls B1, B2∈ B centered at vertices of the form cor c′for the same or different clauses, Tsatisfies the non-clashing condition since T(B1)contains its center (some cor c′) while B2does not contain this vertex. Indeed, the radius of B2is less than 5d, while the distance between any two vertices of the form cor c′is at least 6dsince any shortest path between them contains a vertex from a variable path. For any x, y ∈ X,Tsatisfies the non-clashing condition for B6d(fx)and B6d(fy)since T(B6d(fx)) contains a vertex in Pywhile B6d(fy)does not. For any x∈ X and c∈ C,Tsatisfies the non-clashing condition for B6d(fx)and Brc(c), as well as B6d(fx)and Brc′(c′), since T(B6d(fx)) contains fxwhile Brc(c)and Brc′(c′)do not as rc, rc′<5dwhile cand c′are at distance 6dfrom fx. For any x∈ X,Tsatisfies the non-clashing condition for V(G)and B6d(fx)since T(V(G)) contains a vertex in Px while B6d(fx)does not. Finally, for any c∈ C,Tsatisfies the non-clashing condition for V(G)and Brc(c), as well as V(G)and Brc′(c′), since, among the variables contained in the clause c,T(V(G)) contains at least one vertex from one of those variable paths whose index satisfies c, and at least one vertex from one of those variable paths whose index does not satisfy c. As can be recalled from the construction, this implies that Brc(c)and Brc′(c′)do not contain the respective vertices. Thus, Tsatisfies the non-clashing property for all pairs of balls in B. Now, we prove the reverse direction, so suppose that (G, B, k)is a YES-instance of NON-CLASH and that Tis the corresponding teaching map. For all x∈ X, in order for Tto satisfy the non-clashing condition for B6d(fx) and V(G), we have that T(V(G)) contains at least one vertex from Pxas B6d(fx)⊂V(G)and V(G)\B6d(fx)is restricted to the vertices in Px. Since k=|X|, we in fact have that T(V(G)) contains exactly one vertex from Pxfor all x∈ X. Extract a variable assignment for ϕfrom T(V(G)) as follows. For each x∈X, assign the variable xthe value of the index of the unique vertex contained in both Pxand T(V(G)). We prove that this is an NAE-satisfying variable assignment for ϕ. W.l.o.g., let c∈ C be a clause containing the variables x, y, z ∈ X. In order for Tto satisfy the non-clashing condition for V(G)and Brc(c),T(V(G)) must contain at least one vertex in Px,Pyor Pzthat is not contained in Brc(c). Analogously, in order for Tto satisfy the non-clashing condition for V(G)and Br′ c′(c′),T(V(G)) must contain at least one vertex in Px,Pyor Pzthat is not contained in Br′ c′(c′). Recall that all of the vertices in Px, Py, and Pzthat are not contained in Brc(c)have respective indices that correspond to the respective variable values that satisfy the clause c. Similarly, recall that all of the vertices in Px,Py, and Pzthat are not contained in Brc′(c′) have respective indices that correspond to the respective variable values that do not satisfy the clause c. As these arguments hold for any clause c∈ C, the variable assignment extracted above corresponds to an NAE-satisfying variable assignment for ϕ. Now, we are ready to proceed with the proof of Theorem 19. 16 Proof of Theorem 19. Lemma 20 establishes the correctness of the polynomial-time reduction from the beginning of Section 5. To complete the proof, it remains to show that fvs(G) + pw(G) + kis bounded above by a function of |X|. This clearly holds for kwhich is, by definition, |X|. Deleting from Gthe vertices x1,xd, and fxfor all x∈ X results in an acyclic graph G′; in particular Ghas a feedback vertex set of size 3|X|. To establish a bound on pw(G), it now suffices to show that G′also has bounded pathwidth. Note that G′consists of a set of connected components, each of which is either a subdivided caterpillar (this is what remains of each component containing a variable path) or a vertex (of the form cor c′) with multiple pendent subdivided caterpillars and (simple) paths. Since deleting one further vertex from each connected component may only reduce the pathwidth by 1and we need a single such deletion operation to reach a graph class of constant pathwidth (see Section 2), we also obtain that pw(G)is bounded by a function of |X|. 6 Concluding Remarks Our computational upper and lower bounds provide a near-comprehensive understanding of the complexity of computing the positive non-clashing teaching dimension. Apart from our contributions to the previously studied strict setting, we consider it notable that our work is the first to also tackle the complexity of non-clashing teaching in the non-strict setting—i.e., the more general (and arguably more natural) case where not all possible concepts are present. One open question highlighted by our work concerns the tiny remaining gap between the algorithmic lower and upper bounds obtained in Theorem 4 and Proposition 5. In particular, is there a way to improve the running time of the latter algorithm to 2O(|V(G)|·d·k)and make the bounds tight? More general directions for future work are to perform a similar complexity analysis in the non-positive setting and to consider approximation algorithms. Acknowledgements This work was funded by the Austrian Science Fund (FWF) [10.55776/Y1329 and 10.55776/COE12], the WWTF Vienna Science and Technology Fund (Project 10.47379/ICT22029), the European Union’s Horizon 2020 research and innovation COFUND programme LogiCS@TUWien (grant agreement No 101034440), the Spanish Ministry of Economic Affairs and Digital Transformation and the European Union-NextGenerationEU through the project 6GRIEMANN (TSI-063000-2021-147), and the Smart Networks and Services Joint Undertaking (SNS JU) under the European Union’s Horizon Europe and innovation programme under Grant Agreement No. 101139067 (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 can be held responsible for them. References [ACYT12] 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 International Conference on Human-Robot Interaction (HRI 2012), pages 391–398, 2012. [Ang80a] Dana Angluin. Finding patterns common to a set of strings. Journal of Computer and System Sciences, 21:46–62, 1980. [Ang80b] Dana Angluin. Inductive inference of formal languages from positive data. Information and Control, 45:117–135, 1980. [BDL98] Shai Ben-David and Ami Litman. Combinatorial variability of Vapnik-Chervonenkis classes with applications to sample compression schemes. Discrete Applied Mathematics, 86:3–25, 1998. [BGS23] Cornelius Brand, Robert Ganian, and Kirill Simonov. A parameterized theory of PAC learning. In Proc. of the 37th AAAI Conference on Artificial Intelligence (AAAI 2023), pages 6834–6841, 2023. 17 [BHMvL16] Karl Bringmann, Danny Hermelin, Matthias Mnich, and Erik Jan van Leeuwen. Parameterized complexity dichotomy for steiner multicut. Journal of Computer and System Sciences, 82(6):1020–1043, 2016. [BN19] Daniel S. Brown and Scott Niekum. Machine teaching for inverse reinforcement learning: Algorithms and applications. In Proc. of the 33rd AAAI Conference on Artificial Intelligence (AAAI 2019), volume 33, pages 7749–7758, 2019. [CCM+23] J´ er´ emie Chalopin, Victor Chepoi, Fionn Mc Inerney, S´ ebastien Ratel, and Yann Vax` es. Sample compression schemes for balls in graphs. SIAM Journal on Discrete Mathematics, 37(4):2585–2616, 2023. [CCMR24] J´ er´ emie Chalopin, Victor Chepoi, Fionn Mc Inerney, and S´ ebastien 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, pages 840–875, 2024. [CCMW22] J´ er´ emie Chalopin, Victor Chepoi, Shay Moran, and Manfred K. Warmuth. Unlabeled sample compression schemes and corner peelings for ample and maximum classes. Journal of Computer and System Sciences, 127:1–28, 2022. [CFK+15] Marek Cygan, Fedor V. Fomin, Lukasz Kowalik, Daniel Lokshtanov, D´ aniel Marx, Marcin Pilipczuk, Michal Pilipczuk, and Saket Saurabh. Parameterized Algorithms. Springer, 2015. [CSM+18] Yuxin Chen, Adish Singla, Oisin Mac Aodha, Pietro Perona, and Yisong Yue. Understanding the role of adaptivity in machine teaching: The case of version space learners. In Advances in Neural Information Processing Systems (NeurIPS 2018), volume 31, pages 1483–1493, 2018. [DDvtH16] P˚ al Grøn˚ as Drange, Markus S. Dregi, and Pim van ’t Hof. On the computational complexity of vertex integrity and component order connectivity. Algorithmica, 76(4):1181–1202, 2016. [DEF93] Rodney G. Downey, Patricia A. Evans, and Michael R. Fellows. Parameterized learning complexity. In Proc. of the 6th Annual ACM Conference on Computational Learning Theory (COLT 1993), pages 51–57, 1993. [Den01] Franc¸ois Denis. Learning regular languages from simple positive examples. Machine Learning, 44:37– 66, 2001. [DF13] Rodney G. Downey and Michael R. Fellows. Fundamentals of Parameterized Complexity. Texts in Computer Science. Springer, 2013. [Die24] Reinhard Diestel. Graph Theory, 6th Edition, volume 173 of Graduate texts in mathematics. Springer, 2024. [EGK+23] Eduard Eiben, Robert Ganian, Iyad A. Kanj, Sebastian Ordyniak, and Stefan Szeider. The computational complexity of concise hypersphere classification. In Proc. of the International Conference on Machine Learning (ICML 2023), volume 202 of Proceedings of Machine Learning Research, pages 9060–9070, 2023. [EOPS23] Eduard Eiben, Sebastian Ordyniak, Giacomo Paesani, and Stefan Szeider. Learning small decision trees with large domain. In Proc. of the 32nd International Joint Conference on Artificial Intelligence (IJCAI 2023), pages 3184–3192, 2023. [FKS+23] Shaun Fallat, David Kirkpatrick, Hans U. Simon, Abolghasem Soltani, and Sandra Zilles. On batch teaching without collusion. Journal of Machine Learning Research, 24:40:1–40:33, 2023. [Flo89] S. Floyd. Space-bounded learning and the Vapnik-Chervonenkis dimension. PhD thesis, U.C. Berkeley, 1989. 18 [FS89] Michael R Fellows and Sam Stueckle. The immersion order, forbidden subgraphs and the complexity of network integrity. J. Combin. Math. Combin. Comput, 6(1):23–32, 1989. [GHK+22] Tatsuya Gima, Tesshu Hanaka, Masashi Kiyomi, Yasuaki Kobayashi, and Yota Otachi. Exploring the gap between treedepth and vertex cover through vertex integrity. Theoretical Computer Science, 918:60–76, 2022. [GK95] Sally A. Goldman and Michael J. Kearns. On the complexity of teaching. Journal of Computer and System Sciences, 50(1):20–31, 1995. [GK21] Robert Ganian and Viktoriia Korchemna. The complexity of Bayesian network learning: Revisiting the superstructure. In Advances in Neural Information Processing Systems (NeurIPS 2021), volume 34, pages 430–442, 2021. [GM96] Sally A. Goldman and H. David Mathias. Teaching a smarter learner. Journal of Computer and System Sciences, 52(2):255–267, 1996. [GO24] Tatsuya Gima and Yota Otachi. Extended MSO model checking via small vertex integrity. Algorithmica, 86(1):147–170, 2024. [GRSZ17] Ziyuan Gao, Christoph Ries, Hans U. Simon, and Sandra Zilles. Preference-based teaching. Journal of Machine Learning Research, 18:1–32, 2017. [HLM+16] Mark K. Ho, Michael Littman, James MacGlashan, Fiery Cushman, and Joseph L. Austerweil. Showing versus doing: Teaching by demonstration. In Advances in Neural Information Processing Systems (NeurIPS 2016), volume 33, pages 3027–3035, 2016. [HLVY24] Tesshu Hanaka, Michael Lampis, Manolis Vasilakis, and Kanae Yoshiwatari. Parameterized vertex integrity revisited. In Proc. of the 49th International Symposium on Mathematical Foundations of Computer Science (MFCS 2024), volume 306 of LIPIcs, pages 58:1–58:14. Schloss Dagstuhl - LeibnizZentrum f¨ ur Informatik, 2024. [IPZ01] Russell Impagliazzo, Ramamohan Paturi, and Francis Zane. Which problems have strongly exponential complexity? Journal of Computer and System Sciences, 63(4):512–530, 2001. [KSZ19] 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, pages 506–528, 2019. [KW07] Dima Kuzmin and Manfred K. Warmuth. Unlabelled compression schemes for maximum classes. Journal of Machine Learning Research, 8:2047–2081, 2007. [LL18] Yuanzhi Li and Yingyu Liang. Learning mixtures of linear regressions with nearly optimal complexity. In Proc. of the 31st Conference on Learning Theory (COLT 2018), volume 75 of Proceedings of Machine Learning Research, pages 1125–1144, 2018. [LW86] N. Littlestone and M. K. Warmuth. Relating data compression and learnability. Unpublished, 1986. [MCV+19] Farnam Mansouri, Yuxin Chen, Ara Vartanian, Jerry Zhu, and Adish Singla. Preference-based batch and sequential teaching: Towards a unified view of models. In Advances in Neural Information Processing Systems (NeurIPS 2019), volume 32, pages 9195–9205, 2019. [MZ15] Shike Mei and Xiaojin Zhu. Using machine teaching to identify optimal training-set attacks on machine learners. In Proc. of the 29th AAAI Conference on Artificial Intelligence (AAAI 2015), volume 29, pages 2871–2877, 2015. [OS21] Sebastian Ordyniak and Stefan Szeider. Parameterized complexity of small decision tree learning. In Proc. of the 35th AAAI Conference on Artificial Intelligence (AAAI 2021), pages 6454–6462, 2021. 19 [Sim23] Hans U. Simon. Tournaments, johnson graphs, and NC-teaching. In Proc. of the 34th International Conference on Algorithmic Learning Theory (ALT 2023), volume 201 of Proceedings of Machine Learning Research, pages 1411–1428, 2023. [SM91] Ayumi Shinohara and Satoru Miyano. Teachability in computational learning. New Generation Computing, 8:337–347, 1991. [SO94] Andreas Stolcke and Stephen Omohundro. Inducing probabilistic grammars by Bayesian model merging. In Proc. of the 2nd International Colloquium on Grammatical Inference (ICGI 1994), pages 106– 118, 1994. [SPK00] 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), pages 241–247, 2000. [TC09] Andrea L. Thomaz and Maya Cakmak. Learning about objects with human teachers. In Proc. of the 4th ACM/IEEE International Conference on Human-Robot Interaction (HRI 2009), pages 15–22, 2009. [THF19] Jan Arne Telle, Jos´ e Hern´ andez-Orallo, and C` esar Ferri. The teaching size: computable teachers and learners for universal languages. Machine Learning, 108(8-9):1653–1675, 2019. [WDMH06] Chunlin Wang, Chris Ding, Richard F. Meraz, and Stephen R. Holbrook. PSoL: a positive sample only learning algorithm for finding non-coding RNA genes. Bioinformatics, 22(21):2590–2596, 2006. [YJSS08] Malik Yousef, Segun Jung, Louise C. Showe, and Michael K. Showe. Learning from positive examples when the negative class is undetermined - microRNA gene identification. Algorithms for Molecular Biology, 3(2), 2008. [Zhu15] Xiaojin Zhu. Machine teaching: An inverse problem to machine learning and an approach toward optimal education. In Proc. of the 29th AAAI Conference on Artificial Intelligence (AAAI 2015), volume 29, pages 4083–4087, 2015. [ZLHZ11] Sandra Zilles, Steffen Lange, Robert Holte, and Martin Zinkevich. Models of cooperative teaching and learning. Journal of Machine Learning Research, 12:349–384, 2011. [ZSZR18] Xiaojin Zhu, Adish Singla, Sandra Zilles, and Anna N. Rafferty. An overview of machine teaching. Arxiv:1801.05927, 2018. [ZZW18] Xuezhou Zhang, Xaiojin Zhu, and Stephen Wright. Training set debugging using trusted items. In Proc. of the 32nd AAAI Conference on Artificial Intelligence (AAAI 2018), pages 4482–4489, 2018. 20