The Computational Complexity of Positive Non-Clashing Teaching in Graphs
Authors: Robert Ganian
Liana Khazaliya
Fionn Mc Inerney
Mathis Rocton
Venue: ICLR 2025 Poster (2025)
Keywords: non-clashing teaching
positive teaching
computational complexity
NP-hardness
parameterized complexity
Primary area: learning theory
TL;DR: We obtain a nearly complete understanding of the complexity landscape of computing the positive non-clashing teaching dimension and answer several open questions from the literature.

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 fixed-parameter tractability when parameterized by the feedback vertex number and pathwidth of $G$, even when combined with $k$.
Our results provide a nearly complete understanding of the complexity landscape of computing the positive non-clashing teaching dimension and answer open questions from the literature.

Published as a conference paper at ICLR 2025
THE COMPUTATIONAL COMPLEXITY OF POSITIVE NON-CLASHING TEACHING IN GRAPHS
Robert Ganian, Liana Khazaliya & Mathis Rocton
Algorithms and Complexity Group, TU Wien, Vienna, Austria (rganian, 1khaza i ya, mrocton) ( eewiiiiieetnn...........
Fionn Mc Inerney
Telefónica Scientific Research, Barcelona, Spain fmcinerne gmail 1il...... com
ABSTRACT
We study the classical and parameterized complexity computing the positive non-clashing teaching dimension of set of concepts, that is, the smallest number examples per concept required to successfully teach an intelligent learner un- der 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 instances with positive non non-clashing teaching dimension A and where all balls the graph are present, (2) near-tight running time upper and lower bounds for the problem on general graphs. (3) fixed-parameter tractability when parameter- ized by the vertex integrity of G, and (4) a lower bound excluding exed-paramete tractability when parameterized by the feedback vertex number and pathwidth of G. even when combined with k: Our results provide a nearly complete understand- ing of the complexity landscape of computing the positive non-clashing teaching dimension and answer open questions from the literature.
INTRODUCTION
While typical machine learning models task a learner with finding concept C' from concept class C based on an on-often randomly drawn- in machine teaching (specifically in its com- monly considered batch variant) the learner is provided a set of examples by teacher; crucially, here the examples can be selected in way which allows the concept to be reconstructed from as few examples as possible. Machine teaching is core topic computational learning theory and has found applications in variety of areas including robotics TTomaz & Cakmak 2009 Akgun al. 2012). trustworthy AI (Mei Zhu 2015) Zhang et al.] (2018). inverse reinforvement learning (Ho) al. 2016 Brown & Niekum 2019). and education (Zhu 2015, Chen et al. 2018 Zhu et al. 2018).
While numerous models of machine teaching have been investigated to date (Shinohara Miyano,
1991
Goldman & Kearns [995] Goldman & Mathias [996] Zilles et al.) 2011] Gao et al.) 2017
Mansouri et al. 2019; Telle et al. 2019), in this article we focus on the recently developed positive
non-clashing teaching model (Kirkpatrick al. 2019 Fallat al. 2023)
In non-clashing teaching, given finite binary concept class C, for each pair C1, C2 of distinet con- cepts in C, least one example provided for at least one of C1 or C.2 must 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-Mathia. terion (Goldman & Mathias 1996) 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 the examples provided for each concept C' are required to be positively labeled for C. The restriction of teaching models to the positive setting is common and well-mootvated from applications in, e.g.,
collusion-avoidane cri-
recommendation systems (Schwab al. 2000), computational biology (Wang al. 2006 Yousef jet al., 2008), and grammatical inference (Stolcke Omohundro 1994; Denis] 2001); 1); see also the early works of Angluin (Angluin 1980a b). Non-clashing teaching has been proposed and studied

---

Published as a conference paper at ICLR 2025
in the positive setting not only within the initial papers introducing the concept (Kirkpatrick et al. 2019 Fallat et al. 2023), J but also in subsequent works (e.g.. (Chalopin et al. 2024)).
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, one aims at computing (a witness for) the teaching dimension of given concept class, i.e., the minimum integer l such that each concept is provided with at most le examples 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-specifict graph G, and the possible examples are vertices of G. Indeed, it is known that any finite binary concept class C _ 2Y can be represented by set B of balls in graph G as follows: V(G) = VU (xc C E C), 2c is adjacent to ziçz for all C, C' E C. DC is adjacent to U E V if and only if v E C, and B = [B (xc) C CJ (Chalopin et al. 2023 2024).
On the negative side, the problem is computationally intractable, and remains so even in the re- stricted 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 (2024) recently carried out an initial complexity-theoreti 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 (Impagliazzo et al., (2001), and designed 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 (Chalopin et al. 2024). 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 refer to the problems of computing the positive non-clashing teaching di- mension in the strict and non-strict settings as STRICT NON-CLASH CLASH and Formal definitions complementing the informal descriptions given above are provided in Section 2
respectively.
Our first result concerns the complexity of STRICT NON-CLASH on instances with constant pos- itive non-clashing teaching dimension. The reductions of Chalopin, Chepoi, Mc Inerney, and Ratel (2024) only establish the NP-hardness 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-CLASII is NP-hard or polynomial-time solvable when the sought- after dimension & a fixed constant; the question is not only theoretically interesting, but also highly relevant as instances of small teaching dimension 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 2 is NP-hard-and and remains so even when restricted to the same class of split graphs where STRICT NON-CLAS was previously shown to be NP-hard (for large k) (Chalopin et al. (024)). We note that this result is, in sense, best possi- ble: determining whether an instance of STRICT NON-CLASII has a positive non-clashing teaching dimension of 1 trivial as is equivalent to testing whether G is edgeless (Chalopin et al., 2024).
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 (Impagliazzo et al. 2001). In the preced- ing work, Chalopin, Chepoi, Me Inerney, and Ratel (2024) obtained algorithmic lower and upper bounds of 20(mnd) and (0(n2d)) where n and d are the number of vertices and the diameter of G, re- spectively. From our reduction and a more careful algorithmic analysis, we obtain lower bound of 20(n-d+t) and an upper bound of (10(rdd---logg (Theorem 4 and Proposition m-ammng 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 "wrll-structured" graphs. The more refined parameterized complexity paradigm (Downey & Fellows. 2013, Cygan et al. 2015) offers the perfect tools analyze and identify precisely which structural properties of input graphs graphs-usually usuully captured by a suitable in- teger parameter klallow us to circumvent its general intractability. The analog to the complex-
2

---

Published as a conference paper at ICLR 2025
ity class P in the parameterized setting is FPT ("ftxed-parameter tractable"), which characterizes
parameterized problems solvable in f(k)) n0) 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 (Chalopin et al. 2024)
as well as in a variety of related subfields of learning theory (Downey et al.
1993; & Liang 2018
Ganian & Korchemna 2021 Ordyniak & Szeider 2021 Brand et al., 2023
Eiben et al. 2023a b).
In their previous work, Chalopin, Chepoi, Mc Inerney, and Ratel (2024) established the fixed-
parameter tractability of STRICT NON-CLASI when parameterized by the vertex cover number of the input graph G-or, equivalently, the vertex deletion distance to a graph consisting only of isolated vertices. The drawback of that result is that the vertex cover number is highly "restrictive" parameter, in the sense that it achieves low values only on rather simple graphs. This is also re- flected in the open question posed in that article, which asked about the problem's 's complexity under other parameterizations. As our third contribution, we establish (in Theorem 17 the tixed-paramete tractability of NON-CLASH CLASH -ie. the more general task of computing the non-clashing teaching di- mension 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 (Drange et al., 2016 Gima et al. [022]
Gima & Otachi 2024 Hanaka et al., 2024) that essentially captures the vertex deletion distance to graph consisting only of small connected components; it is known (and easily observed) to be a less restrictive parameterization than the vertex cover number (ef. Section 2). mcaning that our result significantly pushes the boundaries of tractability even for the simpler strict variant of the problem.
The proof of Theorem 17 is highly non-trivial. In particular, while the algorithm itself is simple and merely uses a data reduction technique ("kemelizattio"" " (Cygan et al. 2015)) 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 set of examples for the concepts as witness.
As our final contribution, in Theorem 18 we complement Theorem 17 with a complexity-theoree 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 (Chalopin al., 2024]. We do so through complex W[1]-hardness reduction (which can be seen as a parameterized analog to classical reductions used to establish NP-hardness) that excludes, under well-established complexity assumptions, NON-CLASH from being in FPT even when combining all the parameter- izations 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 KON-CLASH, For instance, the reduction of Kirkpatrick, Simon, and Zilles (2019) Subsection 7.1) establishes that NON-CLASHI is NP-hard even if the task is to deter- mine 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 it simply requires determining whether the input graph is edgeless or not (Chalopin et al. 2024). In fact, unless P = NP, that reduction also rules a polynomial-time apwo-approiinttioon algorithm. For clarity, note that while that duction does not consider concepts that are balls in a graph, as mentioned carlier, every finite binary concept class can be easily transformed into a class of balls in a graph (Chalopin et al. 2023 2024).
Apart from the computational questions resolved in this work, another prominent open question is whether the non-clashing teaching dimension is upper-bounded by the VC-dimension (Kirkpatrick et al. 2019 Fallat et al. 2023, Simon, 2023). 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 (Chalopin et al., 2024). was also pointed out that balls in cacti or planar graphs could be good candidates for concept classes negatively answering this question (Chalopin et al., 2024). Further, Simon (0023) 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 Euclidean space which have been investigated in PAC-Iearning e.g., as part of the more general Dudley concept classes (Floyd 1989 Ben-Davide & Litman| 1998). Apart from non-clan clashing teaching, they have also been explored for the closely related and well-studied sample compression
3

---

Published as a conference paper at ICLR 2025
schemes (Chalopin al., 2023) introduced by Littlestone and Warmuth (1986). As discussed in prior works (Kirkpatrick et al. 2019; Fallat et al. 2023 Chalopin et al.) 2024), non-clashing teach- ing maps can be viewed as signed variants of representation maps for concept classes, notion intro- duced to design unlabeled sample compression schemes for maximum concept classes (Kuzmin & Warmuth 2007) (and subsequently the more general ample concept classes (Chalopin al. 2022
PRELIMINARIES
We assume familiarity with graph terminology (Diestel 2024). We only consider simple, finite, and undirected graphs. For an integer n 2 1, we set [7] ==
{I.....71 nn.. As we only consider finite binary concept classes which can be represented balls in graphs (Chalopin et al. 2023 2024),
introduce the terminology for positive non-clashing teaching directly in the setting of graphs.
POSITIVE NON-CLASHING TEACHING IN GRAPHS. Let G be a graph. For an integer r 2 0 and a vertex E (G), the ball (v) is the set of all vertices at distance at most r from its center v. Let B be set of balls of G. A positive teaching map for ball B E B teaching set T(B) S. B, i.e., subset of the vertices of B. The dimension of T is maxngs (TBB)-inn other words, the largest image T. A positive teaching map T is called non- clashing for B if for each pair of distinct balls Bi, B2 E B, there exists vertex w E T(Bi) (TBBBBUTTA (UT(B2) such that w & B1 n B2. Note that w must lie in B1 U Bg by definition, and hence, this condition ensures that one of the balls has teaching set which is not contained in the other ball. We say that w distinguishes B3 and B2, or distinguishes B₁ from B2 (or vice versa). a teaching map is not non-clashing, we say that there is conflict between any two balls for which there is element distinguishing them. We now define our problems of interest
a mapping which assigns to each
STRICT NON-CLASS
Input:
A graph and an integer k. Is there positive non-clashing teaching map for the set of all balls of G with dimension at most k?
Question:
NON-CLASH
Input:
A graph G, a set B of balls of G, and an integer k. Is there a positive non-clashing teaching map for B with dimension at most k??
Question:
We call teaching map satisfying the conditions of the respective problem statement solution. To avoid any confusion, we remark that the above definitions-ar well as every result obtained in this article- concerns non-clashing teaching the previously studied positive setting.
PARAMETERIZED COMPLEXITY. In parameterized complexity (Downey & Fellows et al. 2015), the running- sunning-times times of algorithms are studied with respect to a parameter p E and input size It is normally used for NP-hard problems, with the aim of finding parameter describing feature of the instance such that the combinatorial explosion is confined to this parameter. A param- eterized problem is pared-prrametrr tractable (FPT) if it can be solved by an algorithm running in time fp) (11, where f is computable function; these are -red-parrmeete algorithms. Proving that a problem is Whr]-hard via a parameterized reduction from a W[1]-hard problem rules out the algorithm under the well-established hypothesis that W[1] * FPT.
2013 Cygan
existence of fixed-paramen
STRICT NON- NON-CLASH is known to be fixed- -aremmerreterr tractable when parameterized by the vertex cover number of G, i.e., the minimum integer such that there is subset X VVG)) of most vertices where G - X is 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 b such that there is vertex subset X C (G) where for every connected component H of G X, (HH) UX| < b;
the feedback vertex number of G (denoted by GG)), which is the minimum integer c such that there is vertex subset X V (G) where G - X is acyclic;
While we decision variants, algorithms are constructive and output a teaching map witness.
4

---

Published as a conference paper at ICLR 2025
the pathwidth of G (denoted by pu(G)), which has involved definition based on the notion of path decompositions. However, for the purposes of this article it is sufficient to note the well- facts (Downey & Fellows 2013 Cygan et al., 2015) that deleting one vertex from each connected component of G will decrease the pathwidth by at most one, and that graph consisting of disjoint union of paths and subdivided caterpillars (i.e., graphs consisting of central path with pendent paths attached to it) has pathwidth 2.
INTRACTABILITY AND RUNNING TIME LOWER BOUNDS
In this section, we establish that STRICT CON-CLASH is NP-hard even when = 2, and thus, that cannot be 1.499-approximated in polynomial time unless P NP. Recall that the former result is tight in the sense that STRICT NON-CLASH is trivial when k = 1 (Chalopin et al., (2024).
Theorem 1. STRICT NON-CLASH is NP-hard even when restricted to split graphs with k = 2.
We prove Theorem | via polynomial-time reduction that, given instance of 3-SAT, constructs an equivalent instance (G, k) of STRIcT NON-CLASH, where G is a split graph and
3-SAT
Input: CNF formula over a set of clauses = {cr,..... :mm] containing variables from X'
fa1,..., Fn), where each clause has exactly literals.
Question: Is there a variable assignment T X + {True, False] satisfying each clause in C?
Reduction. Given instance Figure [b for an illustration).
(C, 2)) of 3-SAT, we construct the graph G as follows (see
(a) The force-gadget. The dotted edge cor- responds to the ab- sence of that edge.
(b) example of the graph G obtained by applying our reduction on the 3-SAT instance with X' = Ly, Fy 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.
Jp} and = {(x: V ny 3q), (æ, a. V w,)).
5

---

Published as a conference paper at ICLR 2025
First, for each E [n]] we create a pair of vertices {ta, fi)- We set A: (t,, fi file
For each i E [n], we introduce variable force-gadger, which consists of set of vertices fr , r2 r"] and edges as depicted in Figure la
For each E [n], we attach the variable force-gadger to the pair (t,, fi} as shown in Figure Tb by making both rī and r! adjacent to both 4 and ft. This gadget will guarantee that the corresponding assignment of the 7th variable is well-defined. We set Rt' ( rf",, rr:" "r""" and R' := (ró) U {r's Hemm), where rig is new vertex.
Similarly, for each & E [m], we introduce clause force-gadget on the set of new vertices {s, $ s%t kk. ) (as depicted in Figure Iaj. This gadget corresponds to the clause Ck of the instance Φ. We add adjacencies according to the appearance of literals in Ct. i.e. 2, E Cg for some i E [ni], then we connect both 8% and s to fūi and if I; Cg. then we connect both sj. and si** to fz. Intuitively, we connect the gadget to those vertices whose underlying assignments (True False for t; and fi, resp.) do not satisfy cj. while the opposite assignments would (see Figure lb). We set 5 == {8% sk **** [ee[m] and
:=
{ U (sLe k[]ke[m). where s is a new vertex.
We add all possible edges between (a) 5 and R"; (b) R and S'; (c) S and R'.
We add all possible edges within S*, and within R*
Lastly, add special vertex and make it adjacent to all the other vertices of the graph.
This concludes the construction of G: given an instance & = (C, 2) of 3-SAT, the reduction outputs the STRICT NON-CLASH instance 2). We now prove its correctness via the next two lemmas. Lemma 2. If o is
of 3-ST, then 2) is a Lemma 3. If (G, 2) is a YES-instance of STRICT NON-CLASII, then & is a YES-instance of 3-SAT.
of STRICT NON-CLASH CLASH.
The proof of Theorem T then follows from Lemma 2 and Lemma 3 In particular, they prove that there is polynomial-time time reduction which transforms any instance of 3-SAT with n variables and m clauses into equivalent instance (G,2) of STRICT NON- CLASH where [V(G) = O(n + m) and G is 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 (G) time would allow us to solve 3-SAT in 20(n+m) time:
Theorem 4. Unless the Exponential Time Hypothesis fails, there is no algorithm solving STRICT NON-CLASH in time (C) where d and k are the diameter of G and the target positive non-clashing teaching dimension of the instance, respectively.
We complement this lower bound with a refined upper bound for the more general NON-CLASE Proposition 5. NON-CLASH can be solved in 20(1 (G))-d-og) (VGG) time.
FIXED-PARAMETER TRACTABILITY VIA VERTEX INTEGRITY
Given that NON-CLASH is NP-hard, it is natural to ask whether the problem can be solved effi- ciently on inputs exhibiting some well-defined structural properties. In this section, we establish the fixed-parameter tractability of NON- CLNCCLASII when parameterized by the vertex integrity of the input graph. Consider an instance (G, B, k) of NON-CLASII and let be the vertex integrity of G. As the first step, we invoke the known algorithm to compute a "witness" for the vertex integrity in time y (( (Fellows & Stueckle 1989), i.e., set X c V(G) such that (V(H) U X| S p for each connected component I of G X. Let H denote the set of connected components of G - X. To make use of the vertex integrity of G, we will partition the components of H. into 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' E H are twin-blocks with respect to B, denoted HI <B H', if there exists an isomorphism &HHH from H to H' with the following properties:
E(G) if and only if oHH E E(G), and for each E (H) and r E N. (u) B if and only if (u), B
for each (H) and X,

---

Published as a conference paper at ICLR 2025
Intuitively, H ~B H' if and only if there is bijection HH. between the vertices of the two subgraphs which preserves (1) edges inside H and H', (2) edges to X, and (3) the existence of balls in B centered the vertices of H and H'. We refer to O.H, as the canonical isomorphism between the two brin-blocks at hand, and if multiple choices of a exist, we choose and fix one arbitrarily; we drop the indices of when the subgraphs H and H', H mg H' can be tested in time at most po(r) by enumerating all possible choices of a.
clear from the context. Observe that for any choice of
Clearly, ~g is an equivalence relation and we denote by [H] the equivalence class containing H. For E V(H), we further define [u] wg {a (u) H' {H]~g] }. and similarly for B, (u) B, [B,(u]]-g = (B') E B w' E [u)=g]: intuitively, these refer to the sets of counterparts of u and (u) in the equivalence class, respectively. For brevity, we overload the notation ~g and use v mg w (or (v) ~g B, (x)) to express that v E [w]~g (or (v) E [B,(w)
respectively).
Observation 6. The number of equivalence classes H. defined by ~B is at most 20("),
While the equivalence relation ~B is defined based on the input (in particular, G and B), our proof requires also considering 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 S of a teaching set T(B) for a ball B = (u) centered in H E a tuple (Sx, Sy) composed of:
1. the set Sx = =T(B)n n X,
2. the set Su = (VH)..
3. the set - Ho E H) functions, where each Ho the function f.o (HHa) + 1,2] specifies whether for a vertex v E V(Ho), the set ([v)~g n T(B)) \ (H) of counterparts of outside of H has size 0, 1 or at least 2.
Intuitively, the blueprint specifies how the teaching set for B interacts with (1) the set X and (2) the vertices inside H itself; 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 3 or 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 H are counted or not.
Lemma 7. Let u E (G), B = (u) E B, and T be a positive non-clasiie can-clahing teaching map for B. Suppose there exist Ho E H. and E V(H)) such that [(])~g n T( 2 3. Then, there exists in [v]~g (BB) such that removing z from T(B) yields a positive non-clashing teaching map for B.
As corollary of Lemma 7 dimension of our instance, which will be useful later in this section.
obtain upper bound on the positive non-clashing teaching
Corollary 8. Let G be a graph with vertex integrity p and B an arbitrary set of balls of G. Then, the positive non-clashing teaching dimension of B is apper-boundee by a function s(p) 20(²))
Returning to the notion of blueprints defined earlier, we can now formalize a refined notion of equivalence that also takes into account the behavior of a hypothetical solution.
Definition 3. Given B = (n) centered in H, and H' ~B H. we say that B and B' = (a(u)) share the same blueprint if. for (Sx, (JHo HoEH) and (8xx Shy, (fHo))ooR)) HoEH), the respective blueprints of B and B', the following hold: (1) Sx = Sxx, (2) Vu V(H), E Su + a(u) E Syy and (3) VHa E H. JH, -JHH.'
Definition 4. Given a positive non-clashing teaching map T for B, we say that two components H. H' E H are serfectly-equivalee twin-blocks (or simply perfectly equivalent) with respect to T on B, denoted H =ī H', if H ~B H' and, for all u E V(H),, r E N, and (u E B, it holds that (u) and (a()) share the same blueprint. Note that = is an equivalence relation.
Crucially, we can also bound the number of equivalence classes for this refined equivalence defined w.r.t. a hypothetical teaching map. We denote the equivalence class of H by [ [
Observation 9. The number of equivalence classes H defined by = is at most 2200%)
7

---

Published as a conference paper at ICLR 2025
With this refined equivalence in hand, we proceed to the second milestone required for our algorithm: a structural result establishing the existence of weell-behaved teaching maps". Roughly speaking, by "well-behaved"
mean teaching maps which only use examples (i.e., vertices) from X and bounded number of "core" components in H. with some controlled exceptions. Toward formalizing this, let us fix an arbitrary total ordering < the components in H..
Definition S. For B E B and x E T(B) n (H)) some H E H. the (B, -core K(B.z) contains the first sp) + elements w.r.t < of {H' E [=] 3B' E [B]=g a(x)) a(x) E T(B)) n (H')). The B-core is the union of the (B,x) -cores for all such x, and the core K. is the union for all B E B of the B-cores.
Definition 6. A component H E H is in the 1-extended core K2 if H E K or there exists B E B and x E V VHH) such that (1) B is centered in K. or in X, and (2) x (B). Going one step step further, component H E H is in the 2-extended core K2 if H E K1 there exists B E B and x E V(H) such that (1) B is centered in Kr or in X, and (2) x E T(B).
For A E (IC K2) note that A is subset of H. but by slight abuse of notation, we will write a E V(A) for x E ((G to denote 3H E with x E V(H) when not leading to any ambiguity. is not difficult to see that the definitions yield the following.
Observation 10. The number of components in K₂ is upper-bounded by c(p) = 22000
We can now formalize the notion of "weell-bhavedd" teaching maps via the property of compactness. Definition 7. A teaching map T is compact if. for any H & H \ K2 and any x E (H), each ball whose teaching set contains x is centered in H.
Our next aim is to prove in Lemma that we can safely restrict our attention to computing compact teaching maps only. Before can establish that result, we first prove two auxiliary statements.
Lemma 11. Let T be a positive non-clashing teaching map for B. Let B E B be centered in HB E H. \ Ki with x T(B) O V(H) for some H H. \ Hn and Hę K(B.a)- By definition, there exists 24 E [x]~~ n (H.). If replacing by x; in TB)) creates conflict, then there exists 2: E T(B) n (...)
Lemma 12. Let T be optimal positive non-clashing teaching map for B, with B E B centered in (BBBVV n (VH)) {H)for for some H E H. \ HA, if (K(B.a)) = s(p) + 1, then there are H; E K(B,.)) and x; E [x]~g n (H:) such that replacing x by x, in T(B) creates no conflict. Lemma 13, If B has positive non-clashing teaching dimension k, then it also admits compact positive non-clashing teaching map of dimension k.
H E H.' \, Kr. For x E T(B)
We now proceed to the crux of our algorithm: the proof that one can reduce the size of the instance (G, without changing its positive non-clashing teaching dimension (formalized in Lemma 15) Toward this, it will be useful to focus on how the balls in B interact with certain subgraphs of G. Definition 8. Let G' be an induced subgraph G. Then, B induuces the set B' of vertex sets w.r.t. G', where B' (B.(u) n (G") (u) E B BAue e V(G')).
We note that B' need not necessarily a set of balls G' itself: for instance, may well happen that for some B E B'' the vertex set B n V(G") is not even connected. However, under some conditions on G' that we will be able to guarantce, B' is, in fact, a set of balls in G'.
Lemma 14. Let G be a graph, B set of balls in G, and G an induced subgruph of G. IfV(G") contains X and, for every H E H. either (I) C (VG) or (2)V(H))V - 0Λ3H', H" e holds, then the set B' induced by B w.r.. G' is a set
[H]~gy HH' + H", ((H)) U UVH") C (G') of balls in G'. Moreover, there is a bijection between balls in B3' and balls in B centered in G'.
We define the reduced graph G' of G as the graph obtained from G by removing all but f(p) <(p) + (P) b(p)
+ twin-blocks from each large class of ~B, where b(p) = O(p²) is the maximum number of distinct balls centered in any component of H. Let B' be the set induced by B on G" according Definition 8 By Lemma 14 1 is set of balls in G'. The size of G' is at most
a(p)
g(p) p ((())) = 22 2 Thus, an optimal positive non-clashing teaching map for B' can be computed (e.g.. by brute force) in time that depends only on p. We now aim at proving that B' is equivalent to B, ie., that the optimal positive non-clashing teaching dimension is the same for both.
8

---

Published as a conference paper at ICLR 2025
Lemma 15. Suppose that there is solution for (G, 13, k). Then, there exists solution T for the reduced instance (G', 1)))..
The following lemma establishes that solution for the reduced instance can be lifted one for the original instance; note that this also ensures that our algorithm will be constructive.
Lemma 16. Let lc E N and T be compact solution the instance (G', We can construct a compact solution T for (G,B, k) in 2206?) (V(G)))))) time.
Finally, we obtain our main parameterized tractability result by combining the previous ingredients. In particular, in the proof, we construct (G', B', k), solve the problem there, and argue correctness.
Theorem 17. NON-CLASE is FPT parameterized by the vertex integrity of the input graph G.
HARDNESS FOR CLASSICAL STRUCTURAL PARAMETERIZAATIONS
In this section, prove that NON-CLASII is intractable w.r.t. the feedback vertex number and pathwidth; the same then holds for generalizations of these measures like treewidth or clique-width. Theorem 18. NON-CLASII is W[I]-hard parameterized by fvs(G) + p +.
We establish Theorem 18 by describing parameterized reduction below and proving its correct-
ness in Lemma 19 We reduce from problem called MAAE-INTEEER---- ---STTT, which is W[r]-hard parameterized by the number of variables (Bringmann et al. 2016), and is defined as follows.
NAE-INTEGER-3
Input: A set of clauses C over variables X, and an integer d. Any clause C has the form x S Cz. 1/ S Cy. and z S Cs. where Cz2 Cys C2 E [l,...,dd d].
Question: Is there a variable assignment X - {1, {l...., d) such that for each clause, either 1 or 2 of its three inqqualities are satisfied?
The Reduction. Given an instance d of NAE-INTEGEER-3SSA we construct an instance (G, of MoN-CLASH in polynomial time as follows, starting with the graph G.
B, k)
For each variable x E X, make (variable) path p == (#1...., ra) of order
For each clause e E C, make two vertices e and c' and, w.l.o.g.,, suppose that the clause contains the variables x, y. and 2, and that Cg S Gy I cg. Connect the vertex e to Ta Mds and 2 by three distinct paths of lengths 4d, 4d + C.. - Cz. and 4d + C₂ cu. respectively" These long paths ensure that there no unwanted shortcuts in G and that, for To 5d - Car - 1, the ball Br, (c) contains all of p py, and Pa except for their first Ca. Cy and C₂ vertices (whose respective indices correspond the respective variable values that satisfy the clause c). respectively. Similarly, connect the vertex c' to V1, and žj by three distinct paths of lengths 4d + c₂ Cz. 4d + C. - Cg. and 4d, respectively. Analogously, this ensures that, for r' = 4d + - 1, the ball B, (c') contains the opposite vertices to B,, (c) in Ps py, and pa (whose respective indices correspond to the respective variable values that do not satisfy the clause c), while ensuring that no unwanted shortcuts exist in
For each clause e E C and each variable q E X such that e does not contain q, G, connect the vertices and c' to by distinct paths of length 3d. These paths ensure that the balls (c) and B,, (c') described above contain every other variable path completely, while ensuring that no unwanted shortcuts exist G.
Let S be the set of all the vertices that currently exist in G. For each x E X, in G, make a vertex fa and connect it to each vertex in S except those in pz via a distinct path of length 6d. Finally, for all x. E X, make fa adjacent to fg. This ensures that, for each x E X, the ball (fa(fz) contains every vertex in G except for those in pa, while ensuring that no unwanted shorteuts exist in G. This completes the construction of G (see Figure
Set ls
|x) Let B consist of (GG,, (fa for all X, and By,(c) and B (c') for all c C.
""Connect vertices u, by a path of length p" means make and the endpoints of path of length p.

---

Published as a conference paper at ICLR 2025
fa
dlege
Ad Ad- Ce
fi
4d
-71
V/1
91
212
1/2
92
ye.
B2 1
Dcc
96
(0
Rc..
Vd-
-d-1
Tdd
yd
7d
9d
Ad + Cy Rr
4el + 0. - 64
Arl
Figure 2: Colorful edges denote paths of the depicted lengths. Two black curves separate the clique from the rest of the graph. Each dotted edge shows that vertex of the clique is adjacent to all the vertices of the graph below the separating curves except those in the adjacent rectangle. The gray curve gives an intuition of which vertices of Pa, Py, and Pz are contained B,, (c) and B (d).
Correctness of the Reduction. Suppose, given instance of NAE-INTEGER---SATT that the reduction from the subsection above returns (G, B, k) as an instance NON-CLASH, of NAE-INTEGER-- ind only (G, B, k) is YES-instance
Lemma 19. á is of NON-CLASH.
Proof of Theorem 18 Lemma 19 establishes the correctness of the polynomial-tin reduction from the beginning of Section To complete the proof, it remains to show that fvs(G) + pw(G)) + is bounded above by function of |.X This clearly holds for which is, by definition, .2). Deleting from G the vertices 31, Id. and fo for all E X' results in an acyclic graph G": in particular G has a feedback vertex set of size 3/2²) To establish bound on pw(G), now suffices to show that also has bounded pathwidth. Note that G" consists of a set of connected components, each of which either a subdivided caterpillar (this what remains of each component containing variable path) vertex (of the form c') with multiple pendent subdivided caterpillars and (simple) paths. Since deleting one further vertex from each connected component may only reduce the pathwidth by and need single such deletion operation to reach graph class of constant pathwidth (see Section 2) we also obtain that p=(G) bounded by a function X
CONCLUDING REMARKS
Our computational upper and lower bounds provide a coarrccmmeeeensivve understanding the com- plexity 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 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 work concerns the tiny remaining gap between the algorithmic lower and upper bounds obtained 4 and Proposition 55) More general directions for future work are to perform a similar complexity analysis in the non-positive setting and to consider approximation algorithms.
Theorem
10

---

Published as a conference paper at ICLR 2025
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/CT22029)
European Union's Horizon 2020 research and innovation COFUND programme Log- icS @ TUWien (grant agreement No 101034440), the Spanish Ministry of Economic Affairs and Digital Transformation and the European Union-NextGenerationnEE through the project 6G- 110-00630002222--11
the C+
and the Smart Networks and Services Joint Undertaking (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 can be held responsible for them.
RIEMANN
REFERENCES
Baris Akgun, Maya Cakmak, Jae W. Yoo, and Andrea L. Thomaz. Trajectories and keyframes for kinesthetic teaching: human-robot interaction perspective. In Proc. of the 7th ACM/IEEE International Conference Hamann-Rober Interaction (IIII 2012), pp. 391-398, 2012.
Dana Angluin. Inductive inference of formal languages from positive data. Information and Control, 45:117-135, 1980a.
Dana Angluin. Finding patterns common to a set of strings. Journal of Computer and System Sciences, 21:46-62, 1980b.
Shai Ben-David and Ami Litman. Combinatorial variability of Vapnik Chenvinkherss classes with applications to sample compression schemes. Discrete Applied Mathematics. 86:3-25 (6:3,25, 1998.
Comelius Brand, Robert Ganian, and Kirill Simonov. parameterized theory of PAC learning. In Proc. of the 37th AAAI Conference on Artificial Intelligence (AAAI 2023), pp. 6834-6841, 2023.
Karl Bringmann, Danny Hermelin, Matthiss Mnich, and Erik Jan van Leeuwen. Parameterized complexity dichotomy for steiner multicut. Journal of Computer and System Sciences, 82(6): 1020-1043, 2016.
Daniel S. Brown and Scott Niekum. Machine teaching for inverse reinforcement learning: Al- gorithms and applications. 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 on Discrete Mathematics, 37(4):2585- 2616, 2023.
Jérémie Chalopin, Victor Chepoi, Fionn 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.
Yuxin Chen, Adish Singla, Oisin Mac Aodha, Pietro Perona, and Yisong Yue. Understanding the role of adaptivity machine teaching: The case of version space learners. In Advances Neural Information Processing Systems (NeurIPS 2018), volume 31, pp. 1483-1493, 2018
Marek Cygan, Fedor V. Fomin, Lukasz Kowalik, Daniel Lokshtanov, Dániel Marx, Marcin Pilipczuk, Michal Pilipezuk, and Saket Saurabh. Parameterized Algorithms. Springer, 2015.
François Denis. Learning regular languages from simple positive examples. Machine Learning, 44: 37-66, 2001.
Reinhard Diestel. Graph Theory, 6th Edition, volume 173 of Graduate texts in mathematics. Springer, 2024.
11

---

Published as a conference paper at ICLR 2025
Rodney G. Downey and Michael R. Fellows. Fundamentals of Parameterized Complexity. Texts in Computer Science. Springer, 2013.
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), pp. 51-57, 1993.
Pål Grønås Drange, Markus S. Dregi, and Pim van Hof. On the computational complexity of vertex integrity and component order connectivity. Algorithmica, 76(4):1181-1222 2016.
Eduard Eiben, Robert Ganian, Iyad A. Kanj, Sebastian Ordyniak, and Stefan Szeider. The computa- tional complexity of concise hypersphere classification. In Proc. of the International Conference on Machine Learning (ICML 2023), volume 202 of Proceedings of Machine Learning Research, pp. 9060-9070, 2023a.
Eduard Eiben, Sebastian Ordyniak, Giacomo Paesani, and Stefan Szeider. Learning small deci- sion trees with large domain. In Proc. of the 32nd International Joint Conference on Artificial Intelligence (IJCAI 2023), pp. 3184 3192, 2023b.
Shaun Fallat, David Kirkpatrick, Hans U. Simon, Abolghasem Soltani, and Sandra Zilles. On batch teaching without collusion. Journal of Machine Learning Research, 24:40: 14:30:1-40:33, 2023.
Michael R Fellows and Sam Stueckle. The immersion order, forbidden subgraphs and the complex- ity of network integrity. J. Combin. Math. Combin. Comput, 6(1):23-32, 1989.
S. Floyd. Space-bounded learning and the Capnik-Chervonente dimension. PhD thesis, U.C. Berkeley, 1989.
Robert Ganian and Viktoriia Korchemna. The complexity of Bayesian network learning: Revisit- ing the superstructure. Advances Neural Information Processing Systems (NeurIPS 2021), volume 34, pp. 430-442, 2021.
Ziyuan Gao, Christoph Ries, Hans U. Simon, and Sandra Zilles. Preference-based teaching. Journal of Machine Learning Research, 18:1-32, 2017.
Tatsuya Gima and Yota Otachi. Extended MSO model checking via small vertex integrity. Algorith- mica, 1671):147-170, 2024.
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.
Sally A. Goldman and Michael J. Kearns. On the complexity of teaching. Journal of Computer and System Sciences, 50 5011)330-3, 1995.
Sally A. Goldman and H. David Mathias. Teaching a smarter learner. Journal of Computer and System Sciences, 52(2)2255-267, 1996.
Tesshu Hanaka, Michael Lampis. Manolis Vasilakis, and Kanae Yoshiwatari. Parameterized vertex integrity revisited. Proc. of the 49th International Symposium on Matherattcal Foundations of Computer Science (MFCS 2024), volume 306 of LIPlcs, pp. 58:1-58:14, Schloss Dagstuhl Zentrum für Informatik, 2024.
Mark K. Ho, Michael Littman, James MacGlashan, Fiery Cushman, and Joseph L. Austerweil. Showing versus doing: Teaching by demonstration. Advances in Neural Information Process- ing Systems (NeurIPS 2016), volume 33, pp. 3027-3035, 2016.
Russell Impagliazzo, Ramamohan Paturi, and Francis Zane. Which problems have strongly expo- nential complexity? Journal of Computer and System Sciences, 63(4)3512-530, 2001.
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 2025
Dima Kuzmin and Manfred K. Warmuth. Unlabelled compression schemes for maximum classes. Journal of Machine Learning Research, 8:2047-2081, 2007.
Yuanzhi Li and Yingyu Liang. Learning mixtures of linear regressions with nearly optimal complex- ity. In Proc. of the 31st Conference on Learning Theory (COLT 2018), volume 75 of Proceedings of Machine Learning Research, pp. 1 1125-1144, 2018.
N. Littlestone and M. K. Warmuth. Relating data compression and learnability. Unpublished, 1986.
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, pp. 9195-9205, 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.
Sebastian Ordyniak and Stefan Szeider. Parameterized complexity of small decision tree learning. In Proc. of the 35th AAAI Conference on Artificial Intelligence (AAAI 2021), pp. 6454-6462, 2021.
Ingo Schwab, Wolfgang Pohl, and Ivan Koychev. Learning 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.
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, pp. 1411-1428, 2023.
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.
Jan Arne Telle, José Hernández-Orallo, and Cèsar Ferri. The teaching size: computable teachers and learners for universal languages. Machine Learning,
2019.
Andrea L. Thomaz and Maya Cakmak. Learning about objects with human teachers. In Proc. of the 4th ACM/IEE International Conference on Human-Roon Roooot 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, 22521):250- 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.
Xiaojin Zhu. Machine teaching: An inverse problem to machine learning and approach toward optimal education. In Proc. of the 29th AAAI Conference on Artificial Intelligence (AAAI 2015), volume 29, pp. 4083-4087, 2015.
Xiaojin Zhu, Adish Singla, Sandra Zilles, and Anna N. Rafferty, An overview of machine teaching- Arxiv: 2018. URL.htpps://arx...oor//bbb. 10000/091711111
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


Reviews:
[{"review_id": "eeJ0cu2IQ6", "reviewer": "Reviewer_iU1d", "summary": "The paper studies the complexity of computing the positive non-clashing teaching dimension that can be interpreted as the smallest number of examples needed to teach an intelligent learner. The paper models the concept class as the set of all balls of a certain radius k in a graph. (A ball of radius k consists of all vertices at a distance at most k from a vertex v serving as the center of the ball.)\n\nThe paper shows that the problem of computing the positive non-clashing teaching dimension is NP-complete, even when k=2. Previously, the problem was known to be NP-complete in general but not for a constant k.\n\nThe second result are improved upper and lower bounds on the time to solve the problem, as a function of the number of vertices n, diameter of the graph d and the radius of the balls k. Both previous and new bounds are exponential time but the exponents have been improved. For example, the upper bound is improved from 2^{O(n^2 d)} to 2^{O(n d k log n)}.\n\nThe third set of results is about the fixed parameter tractability of the problem. Previous, it was known that the problem is tractable if the vertex cover number of the graph is constant. This paper improves this to the vertex integrity being constant. It also considers several other possible improvements (replacing vertex integrity by smaller graph parameters) and rules them out.", "questions": "What would be concrete consequences of your results that would be interesting to ICLR audience?", "limitations": "", "rating": 6, "confidence": 3, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "Clear improvement over previous work.\nComprehensive set of results, covering the complexity of problem from various angles.\nOriginal technical ideas.", "weaknesses": "Not sure about the fit to ICLR in terms of topic, as the paper proves general complexity-theoretic results but does not consider specific classes of concepts for which the studied questions have interesting implications.", "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": "uU8hIqC0VW", "reviewer": "Reviewer_dmLM", "summary": "The authors present several complexity results on the computation of the teaching dimension in the model of non-clashing machine Teaching.\nRecent results have appeared on the \"strict\" variant of the problem and the authors consider the more general case of the non-strict variant. For the strict variant they also strengthen the previous hardness result by showing NP-hardness also for deciding teaching dimension constant bounds. Under the ETH this is also extended to upper and lower bounds on an optimal algorithm complexity for the problem. \nFor the non-strict variant they present new Fixed parameterized complexity results, with respect to less restrictive parameters (Vertex integrity vs vertex cover number used in previous analogous results for the strict variant). Finaly they show W[1]-hardness w.rt to other parameters.", "questions": "Are there results or ideas about approximation algorithms? Or hardness of approximation?", "limitations": "", "rating": 8, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "Generalization to the non-strict model and strenthening of some hardness and FPT results. \nThe complexity picture of the problem is neater than before.", "weaknesses": "The gap in the upper and lower bounds are significant. I do not think that is a strong result.", "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": "2uBohGtdPv", "reviewer": "Reviewer_QH2t", "summary": "This paper investigates the computational complexity of determining the positive non-clashing teaching dimension for a set of concepts, focusing specifically on its representation as balls within a graph G. \n- The authors show NP-hardness for what is known to be the easier subcase of this problem, where all balls are considered (strict non clash). \n- They supplement this hardness result with a positive result for the more general case (non clash), showing fixed parameter tractability with respect to the vertex integrity of a graph, strengthening previous work which had shown fixed-parameter tractability with respect to the vertex cover number, which upper bounds the vertex integrity. \n- They complement the fixed-parameter tractability result with a hardness result that shows hardness of non-clash with respect to a number of natural alternative parameters: feedback vertex number, pathwidth, and teaching dimension, thus identifying vertex integrity as a key parameter for tractability.", "questions": "- How do these questions of teaching dimension relate to questions studied in one-way communication complexity or sample compression? \n- How does allowing for non-positive examples in the teaching set change the hardness of the problem?", "limitations": "", "rating": 8, "confidence": 3, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "- The paper is clearly written, and answers a number of open questions in the area of machine teaching by strengthening existing results on both the hardness of strict-non-clash, and the fixed-parameter tractability/hardness of non-clash. \n- While I am not very familiar with this area, these strengthenings seemed significant in that they show hardness for the easiest subcase of the problem, thus providing a very strong and previously unknown hardness result, and additionally introduce a novel parameter that seems to capture the tractability of the problem given that a combination of other related parameters still render it intractable. \n- The proof techniques needed to solve these problems are highly non-trivial, relying on a delicate reduction to 3-sat in the case of the NP-hardness result, and a complicated equivalence class argument in the case of the fixed-parameter tractability result. \n- I carefully checked the correctness of the proof of Theorem 1 and was satisfied, but due to the length, have to defer to other reviewers for comments about the correctness of the other proofs.", "weaknesses": "- As someone unfamiliar with the area of machine teaching, I felt that some of the introduction/preliminaries relied too heavily on assuming familiarity with previous work, and would have benefitted from additional explanation within the paper to make it more standalone. In particular, I would have liked a bit more discussion on the equivalence between arbitrary concept classes and balls in graphs. I wasn't even sure what arbitrary concept class meant in this case (binary? finite domain?), and how the distinction between strict-non-clash vs non-clash would map to concept classes. \n- While I was convinced by the novelty/significance of the results, I would defer to someone more knowledgeable about this area on this point, as well as more generally the significance of the question of positive-non-clashing teaching dimension. \n- I feel like the related work could have been more substantial, perhaps discussing related problems in other areas of theory/machine learning. \n- Minor note: There is a typo in the first sentence of section 5", "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": "REVwyGiBNM", "reviewer": "Reviewer_86oC", "summary": "This paper studies and obtains several theoretical results for the non-clashing teaching dimension of a concept class. The positive, non-clashing teaching dimension of a class $\\cal C$, somewhat similar to VC dimension, is the minimum integer $k$ such that the following holds. For each concept in the class there is a unique set of examples associated with it of size up to $k$, so that for every two sets $S_1, S_2$ of examples (for different concepts $C_1, C_2$), the symmetric difference between $S_1$ and $S_2$ is non-zero.\n\nThis notion can equivalently be formulated using balls in graphs, where each concept corresponds to a ball of some radius around some vertex (note that some concepts can strictly contain others, e.g., a ball of radius 2 and a ball of radius 1 around the same vertex). The paper obtains several results about this graph theoretic concept:\n\n1. An NP-hardness result for a strict variant of the non-clashing dimension. It is shown that even determining whether the dimension is at most 2 is NP-hard, resolving a question of Chalopin et al. (COLT 2024).\n\n2. Tighter upper and lower bounds improving upon the aforementioned Chalopin et al. work. The upper and lower bound from the aforementioned work are $2^{O(n^2 d)}$ and $2^{\\Omega(n d)}$ where $d$ is the graph diameter, and the current work obtains upper and lower bound of $2^{O(ndk)}$ where $k$ is the non-clashing dimension.\n\n3. Parametrized results obtaining complexity that depend polynomially on $n$ and exponentially on parameters like the vertex integrity. There are also hardness results for well known parametrized notions such as path-width, and by extension, treewidth and cliquewidth.\n\nFrom the technical perspective, the proofs are rather intricate (especially the lower bound ones, which use careful reductions). I did not verify the full details but the proofs seem believable.", "questions": "What do you think about the practical applicability of this non-clashing teaching notion? What is the next set of results that would allow the community to better appreciate this notion?", "limitations": "", "rating": 6, "confidence": 2, "soundness": 4, "presentation": 3, "contribution": 2, "strengths": "- Novelty: new results on an emerging learning concept, which address open problems from the recent literature.\n\n- Mathematical proofs seemingly of significant depth.\n\n- The paper is generally well written.", "weaknesses": "- Somewhat limited scope, this is a graph theoretic concept that has not been of interest outside a theory sub-community (and as such might be less suitable for a wide audience conference like ICLR). \n\n- The studied notion seems somewhat \"too pessimistic to be interesting\". There is an exponential lower bound on the running time even prior to this work (which was improved by this work). The parameterized complexity upper bounds, although new, depend on parameters that seem to be very large, probably linear in $n$, in \"realistic\" graphs.\n\nEdit on the second bullet: the authors' response helped me contextualize better what this notion aims to capture. I am increasing my score by one point, as this was my main qualm about the 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": {}}]

Author rebuttal:

Decision: Accept (Poster)