The Parameterized Complexity of Computing the VC-Dimension
Authors: Florent Foucaud
Harmender Gahlawat
Fionn Mc Inerney
Prafullkumar Tale
Venue: NeurIPS 2025 poster ()
Keywords: VC-dimension
parameterized complexity
hypergraphs
graphs
treewidth
Primary area: theory
TL;DR: We establish new results on the complexity of computing the VC-dimension, including fixed-parameter algorithms and running time lower bounds under the Exponential Time Hypothesis.

Abstract: The VC-dimension is a well-studied and fundamental complexity measure of a set system (or hypergraph) that is central to many areas of machine learning. We establish several new results on the complexity of computing the VC-dimension. In particular, given a hypergraph $\mathcal{H}=(\mathcal{V},\mathcal{E})$, we prove that the naive $2^{\mathcal{O}(|\mathcal{V}|)}$-time algorithm is asymptotically tight under the Exponential Time Hypothesis (ETH). We then prove that the problem admits a $1$-additive fixed-parameter approximation algorithm when parameterized by the maximum degree of $\mathcal{H}$ and a fixed-parameter algorithm when parameterized by its dimension, and that these are essentially the only such exploitable structural parameters. Lastly, we consider a generalization of the problem, formulated using graphs, which captures the VC-dimension of both set systems and graphs. We design a $2^{\mathcal{O}(\texttt{tw}\cdot \log \texttt{tw})}\cdot |V|$-time algorithm for any graph $G=(V,E)$ of treewidth $\texttt{tw}$ (which, for a set system, applies to the treewidth of its incidence graph). This is in contrast with closely related problems that require a double-exponential dependency on the treewidth (assuming the ETH).

The Parameterized Complexity of Computing the VC-Dimension
Florent Foucaud
Harmender Gahlawat
Université Clermont Auvergne, CNRS, Mines Saint- -ainn-Eteenne Clermont Auvergne INP, LIMOS Clernont-Ferrand, France florent foucaud@uca.fr
Université Clermont Auvergne, CNRS, Mines Saint-Etiemm
Clermont Auvergne INP, LIMOS
ClermonttFerrand, France harmenddergaahaaatttgaaa..
Fionn Me Inerney
Prafulkkumar Tale
Telefónica Scientific Research
Indian Institute of Science Education and Research Pune
Barcelona, Spain fmcinern@gmail. com
Pune, India
prafullkmmareiieerppm... ac in
Abstract
The VC-dimension is well-studied and fundamental complexity measure of a set system (or hypergraph) that is central to many areas of machine learning. We establish several new results on the complexity In particular, given hypergraph H = (V,E), E), prove that the naive 20( Vi-ttme algorithm is asymptotically tight under the Exponential Time Hypothesis (ETH). We then prove that the problem admits 1-additive fieed-parameter approximation algorithm when parameterized by the maximum degree of H and fixed-parameter algorithm when parameterized by its dimension, and that these are essentially the only such exploitable structural parameters. Lastly, we consider generalization of the problem, formulated using graphs, which captures the VC-dimension of both set systems and graphs. We design 2t tw). |V|-time algorithm for any graph G = (V, E¹) of treewidth tw (which, for set system, applies to the treewidth of its incidence graph). This is in contrast with closely related problems that require a double-exponential dependency on the treewidth (assuming the ETH).
computing the VC-dimension.
1 Introduction
Vapnik and Chervonenkis introduced the a measure of the richness of the expressivity set system C C 2", the VC-dimension of C is the size of largest subset S C V that is shattered by C, i.c., such that {C n S C' E C} 25, The VC-dimension has proven to immensely important in numerous fields, including machine learning, geometry, and combinatorics. Notably, the VC-dimension intrinsic to several prominent topics in machine learning, such as e-nets [47]
Dimension (VC-dimension) 75 as
set system. Given non-empty finite set and
sample compression schemes [56], and machine teaching 45
In particular, e-nets are well-studied in learning theory (see, e.g., 22
6
46
66 and have applica-
tions in the adversarial robustness of machine learning models (see, e.g.,
24
59 ). with the seminal
paper by Haussler and Welzi 47 proving the famous e-net theorem, which roughly states that set systems with fixed VC-dimension admit small e-nets. Furthermore, in relation to Valiant's probably approximately correct (PAC) learning 774, the VC-dimension is at the heart of one of the oldest open problems in machine learning: the sample compression conjecture of Floyd and Warmuth [37].
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

This problem asks whether every set system of VC-dimension d admits a sample compression scheme of size (dd. and it is actively pursued to this day, with a plethora of works making progress on over the years (see, e.g..
4
5 16
18
37
48
61
62
67 The VC-dimension is also central
to various machine teaching models and their major open problems. Specifically, Simon and Zilles asked whether every set system of VC-dimension d has recursive teaching dimension (cd) [7]].
and Kirkpatrick, Simon, and Zilles asked whether every such set system has non-clashing teaching dimension at most d [52), with numerous works (see, e.g., [95 26, 36 42 49 57 60 71 72)
making advances toward these questions and related directions. Overall, the fundamental nature of the VC-dimension in these various areas has motivated the study of its computational complexity, with the associated decision problem often equivalently formulated using hypergraphs as follows.
"C-DIMENSION
Input: A hypergraph H. (V,E) and positive integer k. Question:
Does there exist subset S C V such that |S| 2 k and (Sne:e =
is easy to see that VC-DIMENSION can be solved in |7/ (74)) time, i.e., quasi-polynomial time, and thus, is most likely not NP-hard. Papadimitriou and Yannakakis [68] introduced the complexity class LP and proved that VC-DIMENSION is LogNP- -complceee As LogNP lies in between and NP, and both inclusions are believed to be proper, it is unlikely that VC-DIMENSION is in P either. Their result also implies that, assuming the Exponential Time Hypothesis (ETH) (the ETH is a standard conjecture in computational complexity), VC-DIMENSION cannot be solved in | |[]] time. Recently, Manurangsi (58) proved that VC-DIMENSION is highly inapproximable under well-established complexity-theorete hypotheses, even ruling out a polynomial time approximation algorithm with oloo (7l) approximation factor, assuming the Gap- ETH (a strengthening of the ETH).
Our Contributions. We make further progress on the complexity of computing the VC-dimension. We first complement the result of Papadimitriou and Yannakakis by proving that the naive brute-force 20(VV--imme algorithmr) _ for VC-DIMENSION- that tests each possible subset of V to see whether it shattered has tight running time under the ETH (Theorem 9)
Together with the hardness results from the literature, this motivates studying the parameterized complexity 225 29] of VC--DMMENSON Indeed, this paradigm allows for a refined analysis of the computational complexity of a problem by measuring its complexity not only with respect to the input size T, but also integer parameter l that either originates from the problem formulation or captures well-defined structural properties of the input. The aim for such a parameterized problem is to design an algorithm solving it in f()) [2)((1) time for a computable function f: this is known as a fixed- parrametrrr algorithm. Parameterized problems that admit such algorithm are called tractable (FPT) with respect to the considered parameter. Under standard complexity assumptions, parameterized problems that are hard for the complexity class W[1] are not FPT.
In the above setting, Downey, Evans, and Fellows 28 proved that VC-DIMENSION is W[1 ]-Jompleeee when parameterized by the solution size k. and Manurangsi (58 even ruled out an FPT approximation algorithm with factor olk), ) assuming the Gap-ETH. However, apart from a result of Drange, Greaves, Muzi, and Reidl (30) proving that VC-DIMENSION is W[1]-hard parameterized by the degeneracy of the hypergraph H. little is known about structural parameterizations of VC-DIMENNSON.
We perform systematic analysis in this direction. We prove that there is an FPT 1-additive approximation algorithm for VC-DIMENSION parameterized by the maximum degree A of H (Theorem 12). i.e., it computes a shattered set of size at least VC-dimension minus one. It can also be observed that VC- ICC-DMMENSION is FPT parameterized by the dimension D of H. i.e. the maximum size of hyperedge in H. Indeed, any shattered set is contained within a hyperedge of H. Thus, one can test whether any of the at most 2 possible subsets of any hyperedge is shattered in 2D. [ time. Unfortunately, we prove that the remaining core structural hy hypergraph parameters (hypertree- width and transversal number) do not yield FPT algorithms for VC-DIMENSION (Proposition B
In search of more exploitable structural parameters, we turn our attention to the VC-dimension in graphs. The VC-dimension of a graph G = (V, E) is the VC-dimension of the set system whose ground set is V and whose sets all the open neighborhoods of the vertices in V. The problem GRAPH- VC-DIMENSION is defined similarly to VC-DIMENSION, but for graphs: it takes a graph G and integer lo input, and asks whether the VC-dimension of G is at least k.
Note that H| 20VD and testing whether set is shattered can be done in polynomial time.

---

GRAPH- VC-DIMENSION is relevant for the numerous applications in machine learning where the data is inherently graph-structured see, e.g., 63]. GRAPH- VC-DIMENSIN is also interesting since instances of VC-DIMENSION can be converted to instances of VC-DMEENN-D indeed, any set system can be equivalently represented by a set of open neighborhoods in a bipartite graph (see, e.g., (52) or a set of closed neighborhoods in a split graph (see, e.g., [T6.. Given set system S 2", the graph G can be created as follows: for all C' E C, there is a vertex ac, and, for all E V. there is a vertex with Ie adjacent to if and only if E C. Then, C' is equivalent to the set of open neighborhoods of vertices in Y := { C E C} in the bipartite graph G. For closed neighborhoods, one needs to make the vertices in Y form a clique (making G' a split graph) and take the closed neighborhoods of the vertices in Y. Both of these set systems are well- established: for open neighborhoods, see, c.g., [9] 40 41 |5| 52 64]. and for closed neighborhoods,
see, e.g. 10 16 22
47 55 The VC-dimension of other graph-related set systems has 72 See [22 30 for experimental evaluations. Due to the equivalence above, we focus on the VC-dimension of open neighborhoods
31
32
also been considered in 11
15
16
20
33
34
55
/ and study a generalization of both VC-DIMENSION and GRAPH- CR-APH-C-DDMENNION formulated using graphs:
GENERALIZED VC-DIMENSION (GEN- VC- VC-DIMENSION)
Input: A graph G = (V, E), two subsets X, Y C V, and positive integer k. Question: Does there exist a subset S Ç X such that [S] 2 k and {S (() : M 28?
Indeed, GRAPH- VC-DIMENSION and VC-DIMENSION are special cases of GEN-VC-DIMENSION any instance (G, k) of GRAPH- VC- IC-DIMENSION corresponds to an instance (G,X= = V.Y A) of GEN-VC DA--V-DDDMENSINN and VC-DIMENSION considers the bipartite incidence graph G of the apply to both VC-DIMENSION and
input set system (as defined above), with X = V and Y {xc C E CJ. Hence, our algorithms for
GEN-VC-DIMENSEE
We focus on the treewidth parameterization, which has been exploited for various machine learning problems, see, e.g.. 22 43 65 69). Treewidth is arguably the most successful graph parameter
due to the celebrated Courcelle's 's theorem [23] which states that any graph property definable in monadic second-order logic can be checked in linear time for graphs of bounded treewidth. In fact, this is the case for the treewidth is a tower of exponentials whose height is a function of the treewidth.
[8 Theorem 6.5]. However, the obtained dependency on
We design a much faster (tw-loog |tme algorithm for BEEN-VC-DIMENSEE (Theorem 19 where tw is the treewidth of G. In particular, this result applies both to GRAPH- VC-DIMENSION and to VC- IC-DIMENSION (where the considered graph is the bipartite incidence graph representation of the set system as described earlier). Thus, this further motivates considering the VC-dimension of open neighborhoods in graphs rather than closed neighborhoods. Indeed, as the treewidth of a split graph is one less than the size of its largest clique, then when considering closed neighborhoods in split graph G. we have that G has small treewidth if and only if Y is small. In contrast, for open neighborhoods in a bipartite graph G, it can be that Y is very large even if G has small treewidth. We also emphasize that the running time of our fixed-praameter algorithm has a relatively low dependency on the treewidth that contrasts with (tight) double -ouble-exponential dependencies on the treewidth experienced by recently studied and closely related problems [4 39
Finally, this FPT algorithm is complemented by a lower bound ruling out an algorithm for GRAPHI- VC-DIMENSION running in 2>(ven*k)_ [V]2()) time (Theorem 9). where k is the solution size and vcn is the vertex cover number of G, an even larger parameter than the treewidth of G as vcn 2 tw.
2 Preliminaries
For é E N. let [8] = e) and [0. (0) [e]. Le] Not = NO)
Hypergraphs and Graphs. Let H = (V, be a hypergraph. Set |7d| := |V| + [g). For a vertex V. inc(v) is the set of edges that contain (or are incident) to v. The degree of in H is deg (v) = in)( The maximum degree of 7 is ((H) == max degx(v) (v) (or simply A). The transversal number of H is the minimum size of subset X C V such that X ne # 0 for all E E. If there exists a tree T such that, for all e E &, e is the set of vertices of a subtree of T, then H is hypertree 13 Let G (V, F)) be graph. The open neighborhood of vertex V is the set
We remark that, with minor modifications, many of results also hold for closed neighborhoods.
3

---

N(e) = fu uy E E}, and the degree of v in G is da(u) := [N()). For a subset X _ V. let N X. The closed neighborhood of vertex v E V is the set Mlu] := Ne) {v). For a subset X VVV let G[X] denote the subgraph of G induced by the vertices in X, and let G - X denote the subgraph GIV \ X] of G. A subset U _ is a vertex cover of G if, for each edge in G, at least one of its endpoints is in U. The minimum cardinality of a vertex cover of G' is its vertex cover number (vcn). A subset S t V is a separator if G S contains at least two connected components.
A tree-decompasition of a graph G' is pair (T, 3), where T is tree and 3 V(T) 2V(() is mapping from VTT) (called bags) to subsets of V(G) such that:
1. for all uu E E()), there exists I E (TT) such that {u, v) S 3():;
for all V E VG),, the subgraph of T induced by T. {t E (TT) e B(t) is non-empty tree.
The width of trce-decomposition (T', 9) is (r) [8(+) - 1. The treewidth of G, denoted by tw(G) (or simply tw), is the minimum possible width of a tree-decomposition of G. The mapping | can be extended from vertices of T to subgraphs of T: for a subgraph U' of ((U) Unev(r) B(v). Computing ree-decomposition of minimum width is FPT parameterized by the treewidth [8] (3), and a pree-decomposition of width at most 2tw can be computed in ( [V(G)] time [54]. For dynamic programming, it is useful to have a tree-decomposition with additional properties. A
tree-decomposition (T, B) is nice if each node / E V(T) is exactly one of the following four types:
1. Leaf: is leaf of T and [8(()] 0.
2. Introduce: t has a unique child c and there exists v E V(G) such that ((t) = 3(c) fo).
3. Forget: has a unique child с and there exists v E V(G) such that 8(c) Utt)
4. Join: t has exactly two children c1, 02 and (t)) ((q) B(22).
Let (T.3) () be a (nice) tree decoppoconnn of G and f node of T. The subtree of T rooted at is T₁,
G, = G[T:) G. = G - V(G2), and G = G. B(t). Given a tree-decomposition, we can obtain nice tree-decomposition of the same width and with a linear number of nodes in linear time (25). Thus, a nice tree-dccompositin of a graph G of width at most 2tw and with (V))) nodes can be computed in 20(ww) IV(G)) time. So, if we seek an algorithm with at least that runtime, we may assume that such nice tree-decomposition is part of the input.
Let H = (V, E) be a hypergraph. A set U S. V is a shattered set if, for all U" C U, there exists E & such that U ne U" The VC-dimension of H is the maximum size of shattered set of H. For A C V and A' C A, an edge e witnesses A' in A if e A = A'. Let U be a shattered set of H. Then, there exists set E C & such that, for all U U, there exists an edge e E E' with witnessing U' in U. We call such an E' a shattering set of U, and a minimal shattering set W S E of U is said to be wilness U. Observe that [W] = 21,,, In the context of the VC-dimension of set N of open neighborhoods in a graph G = (V, E). subset of vertices U C V is a shultered set if, for each subset U C U, there exists a vertex w that witnesses U", i.c., (w) E N and No (u = U'.
VC-Dimension.
3 Algorithmic Lower Bounds
In this section, via a reduction from 3-COLORING to GRAPH-VC--IMEEN assuming the ETH [50]. where vcn is the vertex cover number of G. This same reduction proves that, assuming the ETH, VC-DIMENSION cannot be solved in (0)) (H()(()) time. An instance of 3-COLORING consists of graph G", and asks whether G' admits proper coloring with colors. The following is well-known:
we establish that, cannot be solved in 2=(ven+*k. (V)1()) time,
Proposition 1 ((25)). Assuming the ETH, there exists constant e, 0 such that 3- 3-COLORING does not admit an algorithm running in ( (V ((1) time.
Reduction. Given an instance G' of 3CCLORING in time exponential in [V(G") (i.e., 20(1())) time, but the value of the constant will be refined later), our reduction returns an instance (G, k) of GRAPH- VC-DIMENSION, We note that it is expected that this reduction takes super- poper--olynomial time since 3- 3-COLORING is Nardard, while VC-DIMENSION can be solved in quasi- polssi-polyomiiall
'The ETH roughly states that ne- variable and m-clause 3-SAT cannot be solved in 2 time.

---

time, and hence, a polynomial-tin -imem reduction would imply that every problem in NP can be solved
in quasi-polynomic time. Now, for the reduction, fix a constant 0 < 6 < set k = [e V (G") and arbitrarily partition the vertices of V(G") into k parts v.,..., Va, each of size at most p = +
Note that, for all é [k]], there are most 3" possible 3-colorings of G' [V]V For each V,, enumerate each valid coloring of (V),, and add a vertex corresponding to it in U, (which is in G). Thus, in G. for all i [Rc], we have an independent set of vertices U; such that [U,] S 3". Set X = USE[K] Uz- We ensure that X is vertex cover of G. Thus, G may be partitioned into X and an independent set Y. We now specify the vertices in Y, which we partition into three sets [, 12, and /23- For each vertex u E X, add vertex w E 11 adjacent to u. For all distinct i, [k]. we add a vertex w E l2 and make it adjacent to u and v if and only if u and v are consistent with each other, by which we mean the union of their corresponding colorings is proper coloring of G'[V, UVJ. For each A S [k] with | 2 3, we add a vertex E I23 adjacent to each vertex in Uj for j A. This completes our reduction (see Figure TT. We now prove its correctness.
U2, and Uj.
1
U2
U3
X
U
1
123
Figure I: The graph G constructed from G², where X (vertex cover of G) and Y 1, Ul U Ul2 are independent sets, An edge between w E 123 and U; signifies that each vertex in Ug is adjacent to w.
Lemma 2. If G' admits a proper 3-coloring, then G contains shattered set of size k.
Proof. If G' admits a proper 3-coloring, then there exist W1 .......: ; Uy E (VG) such that u, E U, for i E [k] and u1,..., (4g are mutually consistent. We claim that S = {ui,-.., us.. } is shattered set in G. First, by the definition of J, for each u, there a unique vertex w; E T1 such that N(w,) = uy- Second, by the definition of 1g and the fact that the vertices in S are mutually consistent, for every two distinct vertices ug, ú, in S, there is a unique vertex w E l2 such that N(w) = {u, uy). Third, by the definition of I>3 and the fact that each u, comes from distinct U/, for every subset A C S such that |A| 2 3, there is a unique vertex w E 123 such that Ng(w)) (w)) = A. Finally, since we can assume that [X| A (as ls I (V') | and X encodes all possible 3-colorings of [V()') vertices), there at least one vertex w E I1 such that Ns(w) = O. Thus, is a shattered set of size in G. O
Lemma 3. If G contains shattered set of size at least then G' admits proper 3-coloring.
Proof. For clarity, we divide this proof into multiple claims. Let S be shattered set of G such that [S] k. Since G is bipartite graph with bipartition XUY, either S X S C = -1UuU222
Claim 4. SCX.
Proof of Claim. Toward contradiction, let S C Y. For all E S, the degree of is least 2 and thus, e E T23 as the degree of each vertex in Jı and Ty is at most 2. Recall that if a vertex v E I23 adjacent some vertex in Ug, then is adjacent to each vertex in Ug. Hence, any minimal set of witnesses for S contains at most one vertex from each U,. Thus, |S] < log k < k, a contradiction.
Claim 5. For all E [k),, |S Ud| <.
Proof of Claim. Toward a contradiction, suppose that there exists an i E [k] such that | | 2 3. Let x, y, z E S U, be distinct. As they are in S, for each subset A of {æ, y, 2), there is a vertex w E Y (as X is an independent set) such that Ns(w) = A. Thus, there is vertex w E Y such that xr, D E (ww), but = & Nw:). As each vertex In has degree and w has degree least 2, then $ 11 As each vertex in 12 cannot be adjacent to two vertices in the same U,, then & T2. If a vertex in I23 is adjacent to some vertex in U., then it adjacent to each vertex U,, and hence, it is not possible that E 123 either. Thus, we have contradiction.
5

---

Claim 6. For distinct i.j E [k). it is not possible that [ 1 and |S (Snuul > 1.
Proof of Claim. Toward a contradiction, assume that there are distinct E [A] such that |Snu,] > 1 and [S U a, b, x E (w), but y & (w)) As in the proof of Claim 5 w & I1 U due to the degree arguments, and it is not possible that x E (w) but & (ww) if w E I23- Thus, we have contradiction.
1. Let a, b E S n U2 and let 2, E
S
in Ug. Then, there is E Y such that
By Claim 4 S S X. and by Claims 5) and 6 either S contains exactly one vertex from each U4 (for i E [k)) or there is most one j E [] such that |S n Ug] = 2, and, for all i [k] such that A j. |sn U S 1. Next, we show that the latter case is not possible.
Claim 7. For all i E [b). [S 1.
Proof of Clain. Toward a contradiction, suppose that there is unique j E [k] such that |sn = 2. and, for all i E [k] such that i i j. |S S Ui < 1. Note that there is at most one Ug, E [k] such that |SNUe| = 0. Let x. y snu, be distinet. Then, there is vertex w E Y such that Ns(w)= = (z, y)- As in the proof of Claim 5 w & I1 due to its degree, and w & I2 as a vertex in Iz cannot be adjacent each vertex of at least three sets in {UI.... }. and hence, to each vertex of at least two sets in (U1.... Uk } {U²). Thus, if x. y E Ns(w), then there is at least one more vertex U E U/ nS where E [R] \ (i, such that v E (sww). Hence, (w( # (2, y). as e is distinct from x and y. Thus, we have a contradiction. o
to two vertices from the same Uz. Each vertex in I23 is adjacent
By Claim 7 S contains exactly one vertex from each U. To complete our proof, we show that the vertices in 5 are mutually consistent. Toward contradiction, assume that there are distinct y E S such that and y are not consistent. Let x E Uj and y E U, for distinct i E [A:]. As xt y E S, there exists w E Y such that (w) {xr, v). As each vertex in J has degree 1, w & T.. Since each vertex in 123 is adjacent to each vertex of at least three sets in {UI..... )x and S containn at least one vertex from each U,, we have that w & 123. So, w E 1z. By the definition of 12. if w is adjacent to x and y, then x and y are consistent. Thus, all vertices in S are mutually consistent, and so, a coloring corresponding these vertices is proper 3-coloring of G'.
Lemma 8. There exists constant 6 > 0 such that, if the instance (G, k)) of GRAPH- VC-DM--C--IMNNNIOO is solvable in 2 2e (V())))) time, then the instance G' of 3-COLORING is solvable in IV [V(G))((1) time.
Proof. Note that |X| S 3 = 31 [1 S | and |723| ( < 2*
Thus, [V(G) = |X| + +/2 |Taal S 2|||++ ~ + 2* Further, we can assume that 3(3 111 fee [V)))) < 2[er-IV(G')11, otherwise [V'G')| is bounded by constant and we can solve the instance of 3-COLORING by brute force. So, [G) S 2f < 22112
First, construct (G, k) from G' in [VGG)(((1) time. As the instances (G,k) of GEN- VC- DIMENSION and G' of 3-COLORING are equivalent (by Lemmas 2 and 3). then solving (G, k) solves G' too. Assume that we can solve (G. k)) in (G) time, and thus, can solve 3- COLORING on G' in 2e-ven V(G) (()) + IV ((1) time. There exists a constant e > 1 such that < 2 [G Recall that X is a vertex cover of G. Thus, our
2e (G)) + (V(G))(()
running time is most 2 +1 (' (((1) Fix 3 . - We can safely assume that (G')] < 2e, (G()) and (GIV( 2e, ((G)). Replacing these values (including the value of e) in our running time, it is at most 22 220er-IV(G)) = (G')) +2ce1), Since
e >> 1, our running time is at most 2)((G')((4es), For any such constant c, we can set 0 < E1 < 1 such that 4cc < 6g. Thus, if we can solve (G, k) in 2 (V(()) time, then we can solve time.
3-COLORING on G' in 2c-IV( (VG)))0)
Finally, the following theorem a consequence of our reduction, Lemmas 2 and S and Proposi- tion I Also, since l: < ven in our construction, the result for GRAPH. VC--IMENSIOO holds for the combined parameter + ven. Moreover, the lower bound for VC-DIMENSION follows since, from our instance (G, k) of GRAPH- WC-DIMENSION (recall that G is bipartite graph with bipartition

---

XU UUY,, we can create an equivalent instance (H = (V. of VC-DIMENSION in polynomial time as follows: set V V= X and, for all y E Y, create hyperedge containing NY)..
Theorem 9. Assuming the ETH, there exists a constant e 0 such that the following statements hold: (i) SRAAH-VVC-OO VC--DIMNSSIN does not admit an algorithm running in 2 kelven+ (IV ()00)) time,
and (ii) VC-DIMENSION does not admit an algorithm running in 2- (7(000) time.
4 Parameterized Complexity of VC-DIMENSION
In this section, we first provide an FPT 1-additive approximation algorithm for VC-DIMENSION parameterized by the maximum degree A == A(H) of H. As noted before, VC-DIMENSION FPT parameterized by the dimension of H and W-hrdd parameterized by the solution size k (28) and the degeneracy of H. [30]. We then cover the remaining well-studied structural hypergraph parameters by proving that VC-DIMENSION is LogNP- hard, even if H. is a hypertree with transversal number 1.
Toward the approximation algorithm, we observe relationship between shattered set and its witness in H = (). Let S == [ri,.... 4/ C V be a shattered set of H. of size k. and W S & a witness of Note that [W] = 2 and, for each subset S' S S, there exists a unique edge e E W such that ens = 5" In other words, for each A C [k], there exists edge
W such that 0; E e if and W2* of the edges of W such that e E wy (for E [A]] and j E [0, 2* 1)) if and only if the 2th least significant bit of the binary representation of is 1. We call such an ordering good ordering. We observe a usefuu property of this relationship.
only if i E A. Thus, there exists an ordering (Wy,
Lemma 10. Given a hypergraph H = (V,E) and W C E with [W| = 2* one can decide whether there exists a shattered set S - such that |S| = k and W is witness of S in |W|W ((1) time.
Proof. The algorithm is the following. Enumerate all possible orderings of W and, for each ordering (w....., -1) -1) of W, decide whether it is good ordering for some subset S C V as follows: if, for each i E [k:), there exists at least one vertex v E V such that wy E inc(v) n W if and only if the 7th least significant bit of j is 1, then W is a good ordering. From good ordering,
can easily extract a shattered set S which contains exactly one vertex satisfying the condition above for each i e [A]. Since all possible orderings of W can be enumerated in ([W]IW]) time, and, for each ordering. can be checked in polynomial time whether it is good ordering, then it can be decided whether W witnesses some shattered set of size k in [W]I.. [H] (1)) time.
O
Observation 11. Let S C V be non-trivial shattered set of hypergraph H (V, Then, for each verlex e E S, there exists a subset of inc(v) that shatters S {v}.
Proof. Let W C E be a shattering set of S, and let S. = S {o]. Then, for each subset S' C Se. there is an edge e W such that S' [v} = S. Thus, for each subset S' S. Sg, there exists an edge E inc(r) such that e S. = S", and hence, inc(r) contains a subset that shatters Sp.
We now provide an FPT 1-additive approximation algorithm for VC- VC-DIMENSION parameterized by A. It applies the next algorithm at most log A times, since the VC-dimension of H. is at most log A + 1, as any vertex in shattered set of size greater than log A + would need to be in more than 21og A A+1-1 = A hyperedges.
Theorem 12. VC-DIMENSION admits 20 log A). 174100) -ime algorithm that either outputs shattered set of size 1 or certifies that there no shattered set of size ie in H.
Proof. If 7 = (V,E) contains a shattered set S of size k then by Observation 11 there exists S _ V such that subset of inc(v) shatters set of size k - 1. For all V. we look at each subset W S inc(v) of size 2 to decide whether W witnesses a shattered set S C V of size using Lemma 10 and report S if it exists. The correctness of the algorithm follows from Observation I since, if there is shattered set of size at least k, then our algorithm will report shattered set of size k - 1, and if our algorithm fails to find a shattered set of size k: - 1, then it would imply that there is no shattered set of size k in H. Finally, we analyze the running time. For all e E V, we look at all subsets of inc(v) of size 2k-1, and then, for each subset, we invoke the algorithm from Lemma 10 Since inc(e)) < A for each V. we consider at most 2 subsets of inc(v), and as
7

---

the size of each of these subsets is at most A. for each of these subsets we need A -7/100) time. Thus, the total running time is 2 A -1H = 2 log A) |H|0(1)
Theorem 12 also applies to GEN- VC-DIMENSION where the vertices in X have maximum degree at most A. When all vertices in X U Y have maximum degree A (this applies for example to GRAPH- VC-IIMENION for input graphs of maximum degree A), then one can actually obtain an FPT algorithm running in 20 log A) ())() time 3 Theorem 15]. This can even be improved to
20 A) ()o1)o((); observe that the solution must be contained in the neighborhood of some vertex in Y; hence suffices to enumerate, for each such neighborhood (which of size at most A), each of its possible subsets of size log A + and check in polynomial time whether it is shattered.
However, the remaining well-known structural hypergraph parameters do not yield tractability: Proposition 13. VC-DIMENSION is LogNP-hardd even if H is hypertree with transversal number I.
Proof. Given hypergraph H = (V, let Ht -V", be the hypergraph obtained from H by adding a vertex u to each hyperedge. Then, Ht' has the same VC-dimension as H. and H' is hypertree with transversal number (since {u} is a transversal). To see that it is a hypertree, notice that the tree T is the star centered at u whose leaves are V. Since for all e E", we have the vertices form a subtree of
Tractability via Treewidth
In this section, we provide a (tw tw) |V| algorithm to solve CEN-VC-DIMENSION where tw denotes the treewidth of G. For the rest of this section, let (G, X, Y, A) be an instance of GEN-VC- DIMENSION. First, we establish that if a shattered set intersects at least two components of G - Z for some separator Z, then the shattered set is small compared to |Z]:
Lemma 14. Let S be shattered set of G, Z a separator of G. and CI...., Cp the components of G-Z. If there are distinct i.j [p] such that S.C, + 0 and S an C2 + 0, then |S| log [Z] +
Proof. Let v V(C)) and u ns, If vertex æ witnesses subset A C S that contains both u and u, then x is in Z (as Z separates C, and Cý). As there are 2 subsets of 5 that contain both u and there need to be at least 2 2 witnesses in Z. i..., |S| < log Z| + 2.
Let (T, 9) be (nice) tree-eccoppositin of of width tw, and let be a shattered set of G. Similarly to Lemma 14 either there exists bag that completely contains S, or S is small compared to tw: Lemma 15. Let (T, 3) be (nice) tree-decomposition of G of width tw, and let S be a shattered set Gf Then, [S] S log tw or there exists some node u E (TT) such that S C B(v).
Proof. If there exists bag that contains S, then we are done. Hence, we assume that there is no E (TT) such that S C. B(v). and prove that |S| < log tw + 2. Without loss of generality, assume that u and w are two distinct vertices of S that do not appear together in any bag of the tree-decomposition. Further, let & and 12 be two distinct nodes of T such that u E (+1). w E (t2). and l and 12 are at minimum distance in T. Let P be the unique (42 patt in T, and let t be the neighbor of the node t on P. Let Z B(t,) ) n (t)). First, observe that, by our choice of t, t1, and 12, & B(t) and w & ((t)). Hence, u, & Z. Moreover, observe that Z is separator in G (due to the properties of tree-decompositions (25] and u and w are vertices of 5 that appear distinct
components of G Z. Hence, by Lemma 14 we have that |S|| < log Z + 2 < log Iw + 2.
O
We now proceed with the 20 tw) nice tree-decomposition ()) of We compute a nice tree-decomposition of G of width at most
|V algorithm to solve GEN- GEN-VC-DAN W----VCC--DMOOOO given
2tw and with ((Vl) nodes in time 20(tw). [V] (see Section 2). Our algorithm has two phases.
First Phase. First, we assume that shattered set of maximum size is contained in bag of T. Using the technique of 30 Theorem 7] after a pre- preppeccsssigg step that takes (tw). [V] time, for each
'Note that this theorem considers the degeneracy of the graph for the running time, however, for any graph, its degeneracy is most its treewidth. Thus, obtain the runtimes use here.
8

---

node E (T) and each subset S _ ((x) n X,, we check in (0(tw) time whether S is shattered by the vertices of Y. Recall that [V') = (IV')) thus, this phase takes 20(tw) |V] time. If [S] 2 k for any such shattered set S, then we stop and return YES. Otherwise, we move to the second phase.
Second Phase. We may now assume that any shattered set of size in G is not entirely contained within any bag of T. By Lemma [5] if log tw 2 < k; then we return NO. Otherwise, k S log tw+ 2. We now show how we compute a shattered set of maximum size via dynamic programming on the tree-dccomposition in 20(tw-logg (tw-log tw). |VV time, which dominates the runtime of the overall algorithm.
Equivalent Formulation. S S X be shattered set of G such that |S| = k. Then, there exists a set W Y (of witnesses) such that [W] = 2 and, for each subset A C S, there is unique vertex w in W that witnesses A, i.e., NNs = A. Hence, finding a shattered set of size k in G is equivalent to finding S " X and W _ Y such that |S| k. |W] 2", and W witnesses S (see Figure 2 Let us fix a labeling {s1......* } of vertices in S and a labeling {uc1.... (Wye } of vertices in W. This gives us a pattern graph P (the idea of a pattern graph was introduced in (30). Now, if can find
(induced) subgraph H of G with [V(H]] S 2 + k and a function h : V(H) - V(P) such that (i) for any u, V E (H) satisfying h(u)= S and h(v) E W, or vice versa, ue E(H) if and only if h(u)h(v) E E(P), and (ii) for distinct u, u.& E (H) satisfying h(u), h(c) E S or h(u), h(v) E W, h((u) A h(v): then it is easy to see that the vertices of H mapped to S via h form a shattered set. Thus, in our dynamic programming algorithm, we look for such pattern and function in G.
W
117
1/
1/4
W/
W2
W1
S
Figure 2: An illustration for the pattern graph P. Here, S S X, W _ YY and W witnesses S.
Mapping Bags to the Pattern. Consider fixed labeling of SUW {si,.... Sk, w1.... W2 ). and its corresponding pattern P. Our algorithm will check if there is a subgraph of G corresponding to this labeling and pattern. To this end, we define a dynamic programming table (DP table), for which the following function will be useful. For a node E V(T), we have function f (P)) + ((O)U()))) 4J. which assigns each vertex x E W US to vertex in the bag 3(1). or 4. which means that the vertex x is mapped to vertex in G or to 1, which means that I will be mapped to a vertex in G.. Definition 16 (Valid function). Let t be node T. T. A function f (P) B(t) U [1,4) is valid
if the following conditions hold for all i E [k] and j E (2
1. If f(;) (t), then fss) E X. Similarly, if fw)z B(t), then f(w;) EY. If f(s), (w;) E B(t), (i.e., f(si) & {1.4} and f(w;) & (1,43), then f(s.)f(w;)) e E(G) if and only if s;w, E E(P).
3. If sqw, E E()). then neither (s:) =t and f(w,) (4 nor f(s)) =t and f(w,)=+
4. For distinct i, E [k]] if f()). f(sv) E B(t), then f(s.) # f(sv). Similarly, for distinct j.3 E [22*), if ((e,), f(wg)) E B()), then f(w3)) # f(wy.).
Observation 17. For each node t, there are at most (tw (tw+2) possible,function ie., (ow- tw) many functions of the form f (PP) + 3(1) (t.4).
For our bottom-up dynamic programming on 3). we use the notion of extending valid functions,
which, intuitively, "lifts" a valid function f V(P) + B(t) to partial solution of G. (if it exists).
Definition 18 (Extending valid functions). Let be a node of and J :: :VP)) + 3(1) U {t,4) valid function. A function g : V(P) + (G.)) U {t} extends f for all E [K] and j E [2*]:
If f(x:) E B(t) {t), then g(s) = f(s)), and if f(w,) E B(t) U {t), then g(w,) = f(w;). If
f(x)) =1, then g(s)) E Gú, and if f101) =4, then g(w;) E G)-
2. If (f(s)). (G.). then g(s,)g(t,) E(G) if and only if E E(P).

---

3. 1f (P) are two distinct vertices such that g(z), E ((G)), then g(x) # g(v).
DP States. To formally define DP table, we define the DP states. Let t be node of T and f: (:P) - - B(t) U { a function. Then, a DP state l't f) E {0,1], where [(t, f) = implics that f is valid function and there is mapping g : ((P) implies that either f is invalid or f is valid but there is no mapping 9 V(P) + V(G,) that extends f. Next, we explain how we compute
V(G.) that extends f. and [t. f) 0
DP States in bottom-up manner for tree-decomposition.
Leaf Node. For each leaf node I, 3(1) = 0. Thus, the only valid function for / is f V(P) - (t). Furthermore, [(,, f) 1.
Introduce Node. Let be an introduce node and e its unique child such that B(t) 3(c) U {u} for some U E V(G). Two DP states [(t, f) and [[c, f') are introduce compatible if the following hold:
1. f is a valid function for t, and f' is valid function for
If ((x = v (for some x E ((P)), then f'(x) =1 and, for each y E V(P) (x), =f f'(y).
We compute [tt, f) as follows: [[t, f)
V is introduce compatible with (T f'))-
Forget Node. Let t be a forget node which has unique child such that 3(c) (t) U {o} for some U E V(G). Two DP states [t,, f) and (c,, f') are forget compatible if the following hold:
1. f is a valid function for i, and f' is valid function for c.
2. If (x) v (for some x E V()),, then f(x) -4 and, for each y E (VP) \ (æ), f(y) f')))
V We compute (t,, f) as follows: [[,, f) fr is forget compatible withs [")}.
Join Node. Let t have exactly two children c1 C22 and let B(t) = ((a) = ((2)). The DP states T(ei, fi) and T(e2, f2) are join compatible with [tt, f) if the following hold:
1. f. fi, and f2 are valid functions for t, (1, and f2, respectively.
2. For all x E (P), if f()) E B(t [1], then f(x) fz) = f2(x), and if f(x) =J, then either (x) =1 and f2(z) =t, or f1(z) =t and fa(x)= =4.
We compute [[t, f) as follows: [[t, f)
V
{(T(es, fi) A AT(,, fe))}.
fi are compatible f
For the root node r of T, B(r) = 0 and G, G. Also, note that there is a unique valid function f: V(P) + (r)) i.e., for each x E (P), f(x) =J. Now, I'(r,))
1 implies that there is a function g (P)) + V that extends f. and the subset of vertices S C V mapped fsi..... $k] } is a shattered set and the subset of vertices W C V mapped to vertices in (wi..... Wg4 witnesses S. Similarly, if [rr f) = O, then there is no shattered set of size k in G. Since (i) we consider at most (0wt tw) possible functions for each node E V (T) (Observation 17). (ii) all our operations over function require polynomial time in the size of the (at most three) considered bags, and (iii) there are O(VV) bags, we have that the running time of our second phase is 20 tw) [V]. Since phase one requires 20(tw). |V| time, we have the following result.
vertices in
Theorem 19.
admits an algorithm running in 20 tw). [V] time.
6 Conclusion
Computing the VC-dimension a set system or graph has numerous applications in machine learning and other areas. We have advanced the understanding of its parameterized complexity, providing algorithms and conditional lower bounds for several important parameters, including the maximum degree, treewidth (tw), and vertex cover number (ven). The most challenging problem left open by our work is to close the gap between the running time of our 20tt tw). |V|-time algorithm and our 20(ven++& |V)0(1) ETH-based lower bound for GEN- MCs-VC-DIIE VC-DIMENSION, It would also be interesting to know whether our 1-additive FPT approximation algorithm for VC-DIMENSION can be improved to an exact FPT algorithm. Future work could also include studying the setting in which the set system is defined by a circuit, which allows the input size to dependent only on the size of the domain in some cases (70). Notably, our lower bound from Theorem 9 also holds in this setting.
10

---

Acknowledgments and Disclosure of Funding
This work was supported by the French government IDEX-ISITE initiative 16-IDEX-0001 (CAP 20-25), the International Research Center "Innovation Transportation and Production Systems" of the I-SITE CAP 20-25, the ANR project GRALMECO (ANR-2J-CE48-0001) the CNRS IRL ReLaX, the EU Horizon Europe TaRDIS project (grant agreement 10 101093006), and the INSPIRE Faculty Fellowship by DST, Govt of India. We thank Maël Dumas for comments on preliminary version of this manuscript.
References
[1] Martin Anthony, Graham R. Brightwell, and Colin Cooper. The Vapnik-Chervonenkis dimen- sion of random graph. Discrete Math., 138(1-3):43-56, 1995.
[2] Maria-Florina Balcan, Steve Hanneke, and Jennifer Wortman Vaughan. The true sample complexity of active learning. Mach. Learn., 80(2-3):111-133 2010.
[3] Cristina Bazgan, Florent Foucaud, and Florian Sikora. Parameterized and approximation complexity of partial VC dimension. Theor. Comput. Sci., 766:1-15 2019.
[4] Shai Ben-David, Alex Bie, Clément L. Canonne, Gautam Kamath, and Vikrant Singhal. Private distribution learning with public data: The view from sample compression. In Advances in Neural Information Processing Systems 36: Annual Conference on Neural Information Processing Systems 2023, NeurlPS 2023, 2023.
[5] Shai Ben-David and Ami Litman. Combinatorial variability of Vapnik-Chervonenks classes with applications to sample compression schemes. Discrete Appl. Math., 86 86(1):3-25, 1998.
[6] Sujoy Bhore, Devdan Dey, and Satyam Singh. Online epsilon net and piercing set for geometric concepts. In The 1 13th International Conference on Learning Representations, ICLR 2025, 2025,
[7] Anselm Blumer, Andrzej Ehrenfeucht, David Haussler, and Manfred K. Warmuth. Learnability and the Kapnik-Chervonenkis dimension. J. ACM, 36()):92999))) 965, 1989.
[8] Hans L. Bodlaender. A linear-time algorithm for finding tree-decompositiinn of small treewidth. SIAM Comput., 1505):130-1 1996.
[9] Marthe Bonamy, Edouard Bonnet, Nicolas Bousquet, Pierre Charbit, Panos Giannopoulos, Eun Jung Kim, Pawel Rzazewski, Florian Sikora, and Stéphan Thomassé. EPTAS and subexpo- nential algorithm for maximum clique on disk and unit ball graphs. J. ACM, 68(2):9: 2021.
[10] Nicolas Bousquet, Aurélie Lagoutte, Zhentao Li, Aline Parreau, and Stéphan Thomassé. Iden- tifying codes in hereditary classes of graphs and VC-dimension. SIAM J. Discrete Math., 29(4):2047-200 2064, 2015.
[11] Nicolas Bousquet and Stéphan Thomassé. VC-dimension and Erdös-Pósa property. Discrete Math., 33:(122)230222311 2015.
[12] Cornelius Brand, Robert Ganian, and Mathis Rocton. New complexity-theon thhoretic frontiers of tractability for neural network training. In Advances in Neural Information Processing Systems 36: Annual Conference on Neural Information Processing Systems 2023, NeurIPS 2023, 2023.
[13] Andreas Brandstädt, Feodor F. Dragan, Victor Chepoi, and Vitaly I. Voloshin. Dually chordal graphs. SIAM J. Discrete Math., 1133):337-455, 1998.
[14] Dipayan Chakraborty, Florent Foucaud, Diptapriyo Majumdar, and Prafullkumar Tale. Tight (double) exponential bounds for identification problems: Locating-dominating set and test cover. In 35th International Symposium on Algorithms and Computation, ISAAC 2024, volume 322 of LIPles, pages 19:1-19:18. Schloss Dagstuhl Leibniz-Zentrum für Informatik, 2024.
[15] Jérémie Chalopin, Victor Chepoi, Fionn Me Inemnyy and Sébastien Ratel. Non-clashing teaching maps for balls graphs. In The 37th Annual Conference on Learning Theory, COLT 2024, volume 247 of PMLR, pages 840-875, 2024.

---

[16] Jérémic Chalopin, Victor Chepoi, Fionn Mc Inerney, Sébastien Ratel, and Yann Vaxès. Sample compression schemes for balls in graphs. SIAM J. Discrete Math., 37(4):2585 2616, 2023.
[17] Jérémie Chalopin, Victor Chepoi, Shay Moran, and Manfred K. Warmuth. Unlabeled sample compression schemes and corner peelings for ample and maximum classes. J. Comput. Syst. Sci., 127:1-28, 2022.
[18] Zachary Chase, Bogdan Chornomaz, Steve Hanneke, Shay Moran, and Amir Ychudayoff. Dual VC dimension obstructs sample compression by embeddings. In The 37th Annual Conference on Learning Theory, COLT 2024, volume 247 of PMLR, pages 923-946, 2024.
[19] Xi Chen, Yu Cheng, and Bo Tang. On the recursive teaching dimension of VC classes. In Advances in Neural Information Processing Systems 29: Annual Conference Neural Information Processing Systems 2016, NIPS 2016, pages 2164-2171, 2016.
[20] Victor Chepoi, Bertrand Estellon, and Yann Vaxès. Covering planar graphs with fixed number of balls. Discrete Comput. Geom., 37(2):237-244, 2007.
[21] Victor Chepoi, Arnaud Labourel, and Sébastien Ratel. On density of subgraphs of Cartesian products. J. Graph Theory, 93(1):64-87, 87, 2020.
[22] David Coudert, Mónika Csikós, Guillaume Ducoffe, and Laurent Viennot. Practical computation of graph VC-dimension. 22nd International Symposium on Experimental Algorithms, SEA 2024, volume 301 of L/PIcs, pages 8:1-8:20. Schloss Dagstuhl- Leibnni-Zzzi für Informatik, 2024.
[23] Bruno Courcelle. The monadic second-order logic of graphs. I. Recognizable sets of finite graphs. Information and computation, 85(1):12-735 1990.
[24] Daniel Cullina, Arjun Nitin Bhagoji, and Prateek Mittal. PAC-learning in the presence of adversaries. In Advances in Neural Information Processing Systems 31: Annual Conference on Neural Information Processing Systems 2018, NeurIPS 2018, pages 228-239, 2018
[25] Marek Cygan, Fedor V. Fomin, Lukasz Kowalik, Daniel Lokshtanov, Dániel Marx, Marcin Pilipozuk, Michal Pilipczuk, and Saket Saurabh. Parameterized Algorithms. Springer, 2015.
[26] Thorsten Doliwa, Gaojian Fan, Hans Uirich Simon, and Sandra Zilles. Recursive teaching dimension, VC-dimension and sample compression. J. Mach. Learn. Res., 15()):3107-3131 2014.
[27] Justin Domke. Maximum likelihood learning with arbitrary treewidth via fast-mixing parameter sets. Advances in Neural Information Processing Systems 28: Annual Conference on Neural Information Processing Systems 2015, NIPS 2015, pages 874-882, 2015.
[28] Rodney G. Downey, Patricia A. Evans, and Michael R. Fellows. Parameterized learning complexity. In The 6th Annual ACM Conference on Computational Learning Theory, COLT 1993, pages 51-57, 1993.
[29] Rodney G. Downey and Michael R. Fellows. Fundamentals of Parameterized Complexity. Texts in Computer Science. Springer, 2013.
[30] Pål Grønás Drange, Patrick Greaves, Irene Muzi, and Felix Reidl. Computing complexity measures of degenerate graphs. In 18th International Symposium Parameterized and Exact Computation, IPEC 2023, volume 285 of LIPIcs, pages 14:1-14:21. Schloss Dagstuhl- LLiibniz Zentrum für Informatik, 2023.
[31] Guillaume Ducoffe. On computing the average distance for some chordal-like graphs 46th International Symposium on Mathematical Foundations of Computer Science, MFCS 2021, volume 202 of L.Plcs, pages 44:1 14:16.. Schloss Dagstuhl- Leibniz-Zentrum für Informatik, 2021.
[32] Guillaume Ducoffe, Michel Habib, and Laurent Viennot. Diameter computation on H-minor free graphs and graphs of bounded (distance) VC-dimension. In 3/st Annual ACM-SIAM Symposium Discrete Algorithms, SODA 2020, pages 1905-1922, 2020.
12

---

[33] Guillaume Ducoffe, Michel Habib, and Laurent Viennot. Diameter, eccentricities and dis- tance oracle computations on H H-minor free graphs and graphs of bounded (distance) Vapnik- Chervonenkis dimension. SIAM J. Comput., 51(5):1506-1553 1534, 2022.
[34] Lech Duraj, Filip Konieczny, and Krzysztof Potepa. Better diameter algorithms for bounded VC-dimension graphs and geometric intersection graphs. In 32nd Annual European Symposium on Algorithms, ESA 2024, volume 308 of L/Plcs, pages 51:1-51:18. Schloss Dagstuhl Leibniz- Zentrum für Informatik, 2024.
[35] Gal Elidan and Stephen Gould. Learning bounded treewidth Bayesian networks. In Advances in Neural Information Processing Systems 21, Proceedings of the Twenty-Second Annual Conference on Neural Information Processing Systems, NIPS 2008, pages 417-424, 2008.
[36] Shaun M. Fallat, David G. Kirkpatrick, Hans UIrich Simon, Abolghasem Soltani, and Sandra Zilles. On batch teaching without collusion. J. Mach. Learn. Res., 14:40:1140:33: 2023.
[37] Sally Floyd and Manfred K. Warmuth. Sample compression, learnability, and the vapnik- chervonenkis dimension. Mach. Learn., 21(3):269-304, 1995.
[38] Jörg Flum and Martin Grohe. Parameterized Complexity Theory. Texts in Theoretical Computer Science An EATCS Series. Springer Berlin Heidelberg, 2010.
[39] Florent Foucaud, Esther Galby, Liana Khazaliya, Shaohua Li, Fionn Mc Inerney, Roohani Sharma, and Prafullkumar Tale. Problems in NP can admit when parameterized by treewidth or vertex cover. In 51st International Colloquium on Automata, Languages, and Programming. ICALP 2024, volume 297 of LIPIcs. pages 66:1-66:19. Schloss Dagstuhl- Leibniz-Zentrum für Informatik, 2024.
lower bounds
[40] Jacob Fox, János Pach, and Andrew Suk. Hajjs-Hajjal conjecture for graphs with bounded VC-dimension. Discrete Comput. Geom., 61(4))809-82, 2019.
[41] Jacob Fox, János Pach, and Andrew Suk. Bounded VC-dimension implies the Schur-Eree Erdös conjecture. Combinatorica, (1066880--11,, 2021..
[42] Robert Ganian, Liana Khazaliya, Fionn Mc Inerney, and Mathis Rocton. The computational complexity of positive non-clashing teaching in graphs. In The 13th International Conference on Learning Representations, ICLR 2025, 2025.
[43] Robert Ganian and Viktoriia Korchemna. The complexity of Bayesian network learning: Revisiting the superstructure. In Advances in Neural Information Processing Systems 34: Annual Conference on Neural Information Processing Systems 2021, NeurIPS 2021, pages 430-442, 2021.
[44] Sally A. Goldman and Michael J. Kearns. On the complexity of teaching. J. Comput. Syst. Sci., 50(1):20-31, 1995.
[45] Sally A. Goldman, Ronald L. Rivest, and Robert E. Schapire. Learning binary relations and total orders. SIAM J. Comput., 1006) 1993.
[46] Steve Hanneke and Liu Yang. Minimax analysis of active learning. J. Mach. Learn. Res., 16:3487-3602, 2015.
[47] David Haussler and Emo Welzl. Epsilon-nets and simplex range queries. Discrete Comput. Geom., 2:127-151, 1987.
[48] David P. Helmbold, Robert H. Sloan, and Manfred K. Warmuth. Learning nested differences of intersection-closed concept classes. Mach. Learn., 5:165-196, 1990.
[49] Lunjia Hu, Ruihan Wu, Tianhong Li, and Liwei Wang. Quadratic upper bound for recursive teaching dimension of finite VC classes. In The 30th Conference on Learning Theory, COLT 2017, volume 65 of PMLR, pages 1147-1156, 2017.
[50] Russell Impagliazzo and Ramamohan Paturi. On the complexity of k-SAT. J. Comput. Syst. Sci., 62(2)):67-375, 2001.
13

---

[51] Oliver Janzer and Cosmin Pohoata. On the Zarankiewicz problem for graphs with bounded VC-dimension. Combinatorica, 44(4):839 848, 2024.
[52] David G. Kirkpatrick, Hans Ulrich Simon, and Sandra Zilles. Optimal collusion-free free teaching. In Algorithmic Learning Theory, ALT 2019, volume 98 of PMLR, pages 506-528, 2019.
[53] Ton Kloks. Treewidth, Computations and Approximations, volume 842 of Lecture Notes in Computer Science. Springer, 1994.
[54] Tuukka Korhonen. A single-exponentaa time 2-approximation algorithm for treewidth. In 62nd IEEE Annual Symposium on Foundations of Computer Science, FOCS 2021, pages 184-192, 2021.
[55] Evangelos Kranakis, Danny Krizanc, Berthold Ruf, Jorge Urrutia, and Gerhard J. Woeginger. The VC-dimension of set systems defined by graphs. Discrete Appl. Math., 77(3):237-257,
1997.
[56] Nick Littlestone and Manfred K. Warmuth. Relating data compression and learnability. Unpub- lished manuscript, 1986.
[57] Farnam Mansouri, Hans Simon, Adish Singla, and Sandra Zilles. On batch teaching with sample complexity bounded by VCD. In Advances in Neural Information Processing Systems 35: Annual Conference on Neural Information Processing Systems 2022, NeurIPS 2022, 2022.
[58] Pasin Manurangsi. Improved inapproximability of VC dimension and Littlestone's 's dimension via (unbalanced) biclique. In 14th Innovations Theoretical Computer Science Conference, ITCS 2023, volume 251 of L/Plcs, pages 85:1-85:18 8. Schloss Dagstuhl Leibniz--entrum für Informatik, 2023.
[59] Omar Montasser, Steve Hanneke, and Nathan Srebro. VC classes are adversarially robustly learnable, but only improperly. In Conference on Learning Theory, COLT 2019, volume 99 of PMLR, pages 2512-2530, 2019.
[60] Shay Moran, Amir Shpilka, Avi Wigderson, and Amir Ychudayoff. Compressing and teaching for low VC-dimension. In IEEE 56th Annual Symposium on Foundations of Computer Science, FOCS 2015, pages 40-51, 2015.
[61] Shay Moran and Manfred K. Warmuth. Labeled compression schemes for extremal classes. In Algorithmic Learning Theory- 27th International Conference, ALT 2016, volume 9925 of Lecture Notes in Computer Science, pages 34-49, 2016.
[62] Shay Moran and Amir Ychudayoff. Sample compression schemes for VC classes. J. ACM, :3:3):01:1-2::1,, 2016.
[63] Christopher Morris, Floris Geerts, Jan Tönshoff, and Martin Grohe WL meet VC. In In- lernational Conference on Machine Learning, ICML 2023, volume 202 of PMLR, pages 25275-25302, 2023.
[64] Tung Nguyen, Alex Scott, and Paul Seymour. Induced subgraph density. VI. Bounded VC- dimension. arXiv eprint, 2312.15572, 2024. htttps///rxii.. org/ abs/ 2312. 15572
[65] Siqi Nie, Denis Deratani Mauá, Cassio P. de Campos, and Qiang Ji. Advances in learning Bayesian networks of bounded treewidth. In Advances in Neural Information Processing Systems 27: Annual Conference on Neural Information Processing Systems 2014, NIPS 2014, 2014.
pages
[66] János Pach and Gerhard J. Woeginger. Some new bounds for epsilon-nets. In The 6th Annual Symposium on Computational Geometry, SoCG 1990, pages 10-15. ACM, 1990.
[67] Dömötör Pálvölgyi and Gábor Tardos. Unlabeled compression schemes exceeding the VC- dimension. Discrete Appl. Math., 276:102-107, 2020.
[68] Christos H. Papadimitriou and Mihalis Yannakakis. On limited nondeterminism and the complexity of the V-C dimension. J. Comput. Syst. Sci., 53(2):161-170, 1996.
14

---

[69] Mauro Scanagatta, Giorgio Corani, Cassio P. de Campos, and Marco Zaffalon. Learning srewidtt-bbounder Bayesian networks with thousands of variables. In Advances in Neural Information Processing Systems 29: Annual Conference Neural Information Processing Systems 2016, NIPS 2016, pages 1462-1470, 2016.
[70] Marcus Schaefer. Deciding the Vapnik-éervonent dimension Ej-complete. Comput. Syst. Sci., 58(1):177-182 1999.
[71] Hans Ulrich Simon. Toumaments, Johnson graphs and NC-teaching. In International Con- ference on Algorithmic Learning Theory, ALT 2023, volume 201 of PMLR, pages 1411-1428, 2023.
[72] Hans Ulrich Simon. RTD-conjecture and concept classes induced by graphs. arXiv eprint, 2502.09453, 2025. httpss//araii.orrr/b//////00 09453
[73] Hans Ulrich Simon and Sandra Zilles. Open problem: Recursive teaching dimension versus VC dimension. In The 28th Conference on Learning Theory, COLT 2015, volume 40 of JMLR Workshop and Conference Proceedings, pages 1770-1772. JMLR.org, 2015.
[74] Leslie G. Valiant. A theory of the Iearnable. In The 16th Annual ACM Symposium Theory of Computing, STOC 1984, pages 436-445, 1984.
[75] Vladimir N. Vapnik and Alexey Y. Chervonenkis. On the uniform convergence of relative frequencies of events to their probabilities. Theory of Probability & Its Applications, 16(2):264- 280, 1971.
15

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: The abstract and introduction accurately reflect the paper's contributions and the obtained results.
2. Limitations
Question: Does the paper discuss the limitations the work performed by the authors?
Answer: [Yes]
Justification: The work complexity -enpoeiityttheoretic -thooretic in nature, and in this context the limitations are discussed to the same extent as past complexity -thhorrtttt papers at NeurIPS. The paper does not claim any immediate practical applications of the obtained results.
3. Theory assumptions and proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and a complete (and correct) proof?
Answer: [Yes]
Justification: The paper substantiates each formal claim with complete proof.
4. Experimental result reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main ex- perimental results the paper to the extent that affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
Answer: [NA]
Justification: The paper does not include experiments.
5. Open access to data and code
Question: Does the paper provide open access the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, as described in supplemental material?
Answer: [NA]
Justification: The paper does not include experiments.
6. Experimental setting/details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [NA]
Justification: The paper does not include experiments.
7. Experiment statistical significance
Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Answer: [NA]
Justification: The paper does not include experiments.
8. Experiments compute resources
Question: For each experiment, does the paper provide sufficient information the puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Answer: [NA]
Justification:
The paper does not include experiments.
16

---

9. Code of ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurlPS Code of Ethics httpt//s//eerrpp...cccppbbbbbeea
Answer: [Yes]
Justification: The research in the paper conforms with the NeurIPS Code of Ethics.
10. Broader impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [NA]
Justification: Due to the theoretical nature of the studied problem in the paper and the fact that the results are also theoretical, we believe any societal impact would be very unlikely.
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification: The paper does not include any results or content which would require such safeguards, it does contain any real-world data models.
12. Licenses for existing assets
Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Question:
Answer: [NA]
Justification: The paper does not use existing assets.
13. New assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification: The paper does not release new assets.
14. Crowdsourcing and research with human subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well as details about compensation (if any)?
Answer: [NA]
Justification: The paper does not involve crowdsourcing nor research with human subjects. 15. Institutional review board (IRB) approvals or equivalent for research with human subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification: The paper does not involve crowdsourcing research with human subjects.
16. Declaration of LLM usage
Question: Does the paper describe the usage of LLMs if it is important, original, or non-standard component of the core methods in this research? Note that if the LLM is used only for writing, editing, formatting purposes and does not impact the core methodology, scientific rigorousness, or originality of the research, declaration is not required.
Answer: [NA]
Justification: This paper and the research developed for it do not involve LLMs at all.
17


Reviews:
[{"review_id": "0DWvhkHXEE", "reviewer": "Reviewer_HyJm", "summary": "This paper studies the problem of computing the VC dimension of a set system. Let us recall the set up. A set system can be represented as a hypergraph or the corresponding bipartite incidence graph. A subset S of the universe is called \"shattered\" if, for every subset T of S, there is a set in the system whose intersection with S is exactly T. So, in some sense, every subset of S \"appears\" if we restrict the universe (of the set system) to be S. \n\nThe VC dimension is the size of largest shattered set. The computational problem is to compute the VC dimension given an explicit representation of the set system. Note that the largest possible shattered set has size log H, where H is the number of sets in the system. So that automatically gives H^(log H) time algorithms. This is essentially equivalent to also trying out every subset of the system and checking it is shattered.\n\nThere are a series of results:\n \nResult 1. Assuming the Exponential Time Hypothesis, all exact algorithms require 2^{(\\Omega(|V|)} time, where V is the universe.\nResult 2. There is a Delta^D poly(|H|) time algorithm that gives an additive 1-approximation to the VC dimension. Delta is the max degree of the incidence graph.\nResult 3. There is a (tw)^(tw) poly(H) algorithm, where tw is the treewidth of the incidence graph.\n\nResult 1 comes from a reduction from 3-coloring. It goes via a graph VC dimension problem, where the set system is given by the neighborhoods.\nResult 2 comes from ordering ideas (reminiscent of graph degeneracy).\nResult 3 is the most technical, and essentially constructs a dynamic programming solution using the tree decomposition (the typical paradigm).", "questions": "Major:\n\n1. Are there any use cases/applications where one wants to compute the VC dimension of an explicit set system? I think the paper would be stronger with a more compelling case for this problem. I consider NeurIPS a non (purely) theoretical venue. So a purely theoretical justification (as a TCS paper) doesn't seem enough.\n2. Can one improve the Delta^D poly(|H|) to get a dependence on the degeneracy? Certainly seems possible.\n\nMinor:\n\n1. I contest the point that this paper shows that the trivial 2^{(O(|V|)} algorithm is optimal. I suggest that be reworded.\n2. Prop 1 \"Unless the ETH fails, there exists an..\" has double negatives and is hard to parse. I suggest: \"Assume the ETH. Then there exists a constant \\eps such that all algorithms have running time \\Omega(...).", "limitations": "Yes", "rating": 4, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 2, "originality": 3, "strengths_and_weaknesses": "The VC dimension is a fundamental quantity of interest, and it's nice to have a suite of results. The first result on the exponential hardness sets the stage for parameterized algorithms. And both the parameters (degree and treewidth) are natural enough in this setting.\n\nMy primary complaints about the paper are as follows:\n - (Major) Is this the right problem/setting to study? In most VC dimension settings, the number of sets is extremely large and implicitly defined (think halfspaces). So there is often a circuit that describes the set systems. The algorithms described do not (or do they?) port to that setting. It is very rare that one has an explicit set system and wishes to compute the VC dimension.\n - (Minor) It's incorrect to say that the 2^O(|V|) algorithm has been shown to be optimal, assuming ETH. The hardness does not rule out exponential time algorithms with a smaller exponent, which would certainly be useful. The hardness shows that it is unlikely, we can get subexponential dependence.", "was_revised": false, "final_justification": "", "rebuttal": "Thank for your positive review and helpful comments to improve the paper.\n\nMajor Questions:\n\n1. We think that you bring up an interesting question. It is true that when the set system is very large, it is more efficient to represent it as a circuit. However, as pointed out in [1], it is also true that for many set systems, representing them as a circuit can only be done through an exponential blowup in the circuit, negating its utility.\n\nOur work is clearly a theoretical work (as with many other past NeurIPS papers) and we do not claim any immediate real-world applications of our algorithms. As can be seen in our introduction, there are a large number of works that consider the same explicit representation setting as us. Thus, of course there is a choice of which setting to study, but we do not feel that there are very strong arguments to choose one over the other: both are important. It is also difficult to study both in a single work due to space limitations, which is exemplified by past papers on the topic. \n\nNevertheless, we believe that our algorithms may still be useful in some practical settings, especially when the set system (whether provided explicitly or implicitly) has size polynomial in the universe $\\mathcal{V}$. For example, this is the case for set systems of bounded VC-dimension (due to the Sauer-Shelah lemma) or when the set system is a graph. See [2] for a recent work computing the VC-dimension of graph neural networks (GNNs) where they upper bound the VC-dimension by functions of other parameters of the GNN such as the bitlength of its weights. See also [3,4] for recent experimental works computing the VC-dimension of graphs.\n\nMoreover, we do want to point out that our main lower bound result (Theorem 9) also applies to the implicit setting, providing a very valuable lower bound to both settings. Indeed, the excluded runtime is $2^{o(|\\mathcal{V}|)}\\cdot poly(|\\mathcal{V}|)$ since $|H|=poly(|\\mathcal{V}|)$ in our reduction.\n\nConcerning our algorithms, they do not make much sense in the implicit representation of the set system setting since a tree decomposition (whose size depends on the size of the set system) needs to be constructed for our treewidth-based algorithm and we also use the fact that it can be checked whether a set can be shattered in polynomial time in the explicit setting, which is very unlikely to be true in the implicit setting since computing the VC-dimension when the set system is represented by a circuit is $\\Sigma^p_3$-complete (i.e., most likely not in NP) [5]. We believe the latter fact is a big stumbling block that probably rules out most FPT algorithms in the circuit setting, possibly implying that the circuit setting is simply too intractable to be of significant interest from a parameterized complexity perspective. We think it would be an interesting direction to validate or invalidate this intuition in future work, and perhaps there are useful parameterizations that arise from the circuit itself that could be investigated.\n\n2. This is an interesting question, which did not occur to us. Our main aim was to get as close as possible to an FPT algorithm parameterized by the maximum degree since it is known that the problem is W[1]-hard parameterized by the degeneracy (as mentioned in our paper, see reference [29]). However, after checking the literature, it seems that it is not possible to have such an FPT approximation algorithm parameterized by the degeneracy as the aforementioned W[1]-hardness reduction should also rule this out as it is from CLIQUE which cannot be o(OPT)-FPT approximated under the Gap-ETH [5].\n\nWe will incorporate these remarks, which nicely improve the paper.\n\nMinor Questions:\n\n1. Concerning the remark about the $2^{O(|\\mathcal{V}|)}$ algorithm being optimal, assuming the ETH, we will change \"optimal\" to \"asymptotically tight\" to avoid any confusion since of course the big O and little o notations allow for different constants.\n\n2. We will change the statement of Proposition 1 accordingly.\n\nReferences:\n\n[1] M. Schaefer. Deciding the Vapnik-Cervonenkis Dimension is $\\Sigma^p_3$-Complete. J. Comput. Syst. Sci. 58(1): 177-182, 1999.\n\n[2] C. Morris et al. WL meet VC. 40th International Conference on Machine Learning (ICML 2023), pp. 25275-25302, 2023.\n\n[3] D. Coudert et al. Practical Computation of Graph VC-Dimension. 22nd International Symposium on Experimental Algorithms (SEA 2024): 8:1-8:20, 2024.\n\n[4] P. Drange et al. Computing complexity measures of degenerate graphs. 18th International Symposium on Parameterized and Exact Computation (IPEC 2023): 14:1–14:21, 2023.\n\n[5] P. Chalermsook et al. From Gap-ETH to FPT-Inapproximability: Clique, Dominating Set, and More. 2017 IEEE 58th Annual Symposium on Foundations of Computer Science (FOCS 2017), pp. 743-754, 2017."}, {"review_id": "qCjYApQ815", "reviewer": "Reviewer_42Hd", "summary": "The authors introduce the VC dimension for graphs and hypergraphs and show a lower bound on the complexity of computing the VC dimension for graphs conditioned on the exponential time hypothesis.\nThey show this via an exponential time reduction from the 3-Coloring problem.\nThey further show results in parameterized complexity, for the parameters maximum degree and treewidth.\nFor the treewidth result, they provide an explicit dynamic programming approach.", "questions": "Could you please elaborate further on the exponential time reduction? Why can't we just solve 3Col in the reduction? Please elaborate why the use of an exponential time reduction is not problematic.", "limitations": "Yes.", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 4, "clarity": 4, "significance": 3, "originality": 3, "strengths_and_weaknesses": "+: \nThe paper provides a very nice introduction to the subject, such that even those outside the field can follow. \nThe proofs are written clearly, in a step-by-step manner, that is reasonably easy to follow, even considering their at times quite technical nature.\n\n-:\nWhile much of the paper is very clearly communicated, the reasoning and exact nature for the kind of exponential time reduction they use is not explicitly provided.\nI believe that it would be very helpful to the reader to devote a short paragraph to explaining, why exponential time is needed, what kind of exponential time you are considering and why such a reduction gives you the result in the end.\nFurther, a longer conclusion, considering possible impact and tying your work to other results in the area could benefit the paper, although I do realize that space is limited.\n\nminor comments:\nl. 126: Maybe don't use T for the tree, since you used T as a symbol for a subset of V in the sentence before. Using another symbol for either of the Ts could help avoid confusion.\nl. 199: it should be \"i \\in [k]\" instead of \"i \\in [j]\", right?\nl. 294: \"thesesubsets\" -> \"these subsets\"\nl. 300f: I don't understand the sentence inside the parentheses.\nl. 369: \"when it exists\" -> \"if it exists\"", "was_revised": true, "final_justification": "This is a solid paper. The authors have resolved my concerns in their rebuttals.", "rebuttal": "Thank you for your nice review and useful suggestions. We are glad that you appreciated our presentation.\n\nConcerning why the reduction should require exponential time, we will expand on what was written in footnote 4 which appeared at the beginning of the reduction. In particular, we will make a new paragraph before the description of the reduction that explains why it is unlikely to have such a reduction take polynomial time. The reason is that such a polynomial-time reduction would imply that NP=QP due to 3-COLORING being NP-hard and VC-DIMENSION being in QP (solvable in quasi-polynomial time $|H|^{O(\\log |H|)}$). This would be a monumental result as it is not known whether NP=QP and it is widely believed that they are not equal.\n\nIn the reduction description, we will also explicitly state the exponential time the reduction takes (we note that it was already mentioned in the proof of Lemma 8). Lastly, to further clarify why such a reduction gives us the desired result, we will expand on the first sentence of the paragraph before Theorem 9.\n\nAlso, an exponential-time reduction is not problematic in this case since the aim is to exclude the possibility of a certain type of exponential runtime. Thus, all that we require is that the time the reduction takes is at most the exponential runtime that we want to exclude. This is standard for ETH-based reductions just as polynomial time is for NP-hardness reductions, and FPT time is for parameterized reductions (W[1]-hardness).\n\nWe cannot just solve 3-COL in the reduction since by Lemma 8, solving it in the running time that we are trying to exclude for VC-DIMENSION would contradict Proposition 1.\n\nConcerning the conclusion, we will try to extend it as much as possible. As mentioned by other reviewers, it should be a good place to discuss more future directions, such as the case where the set system is defined implicitly rather than explicitly.\n\nLastly, thank you for pointing out the typos and unclear sentence in the minor comments. We will make the appropriate changes."}, {"review_id": "Mow7W9qT1V", "reviewer": "Reviewer_gAYP", "summary": "The paper is a theoretical investigation of the complexity of computing the VC dimension. VC dimension is a key quantity with far-reaching implications so understanding the complexity is a fundamental task and with a long history.\n\nThe authors establish several results:\n\n-Under ETH, the simple algorithm that runs in 2^n time is optimal. This algorithm, given a hypergraph on V vertices, will simply check all subsets of V to see if it's shattered. The main technique here is a clever reduction from the 3-coloring problem and relying on known hardness for the latter.\n\n-Given this, the authors turn to fixed parameter approaches, and show that VC computation depends on the types of parameters used. For some natural choices of them, like maximum degree ∆ of hyperedges, they almost solve the problem by providing a additive-1 approximation. They also analyze the dimension D of the hypergraph, showing FPT algorithms, and also on the negative, other core structural hypergraph parameters (hypertree, width and transversal number) do not yield FPT algorithms.\n\n-Finally, the authors focus on treewidth parameterization and show positive results. The define a slight generalization called GEN-VC-DIMENSION and show it is FPT parameterized by the treewidth tw of G (Theorem 17), in particular they design a 2^O(tw·log tw) · |V |^O(1)-time algorithm. They also show a lower bound based on vertex cover number vc which is always at least as large as tw.", "questions": "minor question that would improve the presentation and highlight novelties in your reductions: compared to the previous works doing FPT algos for VC dimension, it would be nice to have a paragraph or two where you compare not just the results from previous works to yours, but also the techniques as well. For example, the 3-coloring reduction, were there known connections between the two problems?", "limitations": "-it is a theoretical work so yes.", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 4, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "STRENGTHS:\n-they authors solve fundamental problems in the area that should be of broad interest\n-deep set of results combining FPT knowledge and connecting it to VC dimension\n-clever reduction from 3-Coloring to VC dimension computation, this leads to Theorem 9. This is satisfying result given that the naive algorithm appears to be best under ETH in some sense\n-clever usage of treewidth in an algorithmic way to determine the VC dimension\n\nWEAKNESSES:\n-literature comparison at a technical level would be appreciated, see brief question below.", "was_revised": true, "final_justification": "I have read the authors response and maintain my score.", "rebuttal": "Thank you for your kind review and nice suggestion to improve our paper. We are glad that you appreciated our results.\n\nWe will elaborate on the discussion of the related work to add which techniques were used. We remark that there are very few parameterized algorithms for VC-dimension and just a few hardness results, and that was actually a main motivation for the paper. For example, we will highlight that the previous W[1]-hardness results came from reductions from CLIQUE and the previous FPT inapproximability came from a reduction from MAXIMUM BICLIQUE. As far as we know, there were no known prior connections between 3-COLORING and our problem."}, {"review_id": "uTWmGaHZQ5", "reviewer": "Reviewer_KBz3", "summary": "This paper presents a systematic parameterized-complexity study of computing the VC-dimension of set systems (hypergraphs). Building on earlier results that established W[1]-hardness when parameterized by the solution size or the hypergraph degeneracy, the authors obtain several new findings:\n\n- **Maximum degree.** It is 1-additive approximation FPT algorithm when parameterized by the maximum degree of the hypergraph.\n- **Maximum hyperedge size.** It is FPT when parameterized by the largest hyperedge size.\n- **Treewidth.** It is FPT when parameterized by the treewidth of the corresponding bipartite incidence graph.\n- **Hypertree width / transversal number.** It is *not* FPT when parameterized by hypertree width or transversal number, unless LogNP=P\n\nThe paper also explores several variants of the VC-dimension problems.", "questions": "See \"weaknesses\"", "limitations": "yes", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "**Strengths:** By combining new algorithms with matching hardness for a wide range of structural parameters, this paper provides a comprehensive picture on the parameterized complexity of VC-dimension. The results are clearly presented and well organized.\n\n**Weaknesses & Suggestions:** Several questions remain to be explored. For examples,  do the lower bounds still hold when one aims to approximate, rather than exact compute, the VC-dimension?  Clarifying this approximability landscape would further strengthen the contribution.", "was_revised": true, "final_justification": "This paper provides a comprehensive parameterized-complexity analysis of computing the VC-dimension of set systems. The results are technically sound, and the topic is highly relevant to the conference. I am positive about the work.", "rebuttal": "Thank you for your helpful insights to improve the paper, and we are happy to hear that you appreciated the clarity and organization of our paper. \n\nWe will elaborate the discussions around approximability. We recall that we already mentioned inapproximability results from the literature in lines 47-49 and 65-66. We would also get the existing inapproximability results from the literature in Proposition 13. For Theorem 9, we believe the reduction would need to be significantly changed in order to get inapproximability. As mentioned in our response to reviewer HyJm, an existing hardness result from the literature also provides inapproximability, showing that our FPT approximation algorithm is in some sense tight with respect to the choice of parameter. We will make the appropriate changes."}]

Author rebuttal:

Meta-review: This is a well-written paper that studies the parameterized complexity of computing the VC-dimension, a fundamental notion in learning theory and combinatorics. The paper provides both algorithmic and hardness results under natural structural parameters such as maximum degree, hyperedge size, and treewidth.

We recommend acceptance as a poster. The work is technically solid and addresses a fundamental problem with clarity and rigor.

That said, we would like to point out that some doubts were raised during the discussion regarding whether NeurIPS is the most appropriate venue for this type of result. While the VC-dimension plays a central role in understanding generalization in machine learning, the algorithmic problem of computing the VC-dimension is less common in practical ML applications.

We thank the authors for their contribution.
Decision: Accept (poster)