# Estimating VC-Dimension

What is known about the following problem?

Given a collection $C$ of functions $f:\{0,1\}^n\rightarrow\{0,1\}$, find a largest subcollection $S \subseteq C$ subject to the constraint that VC-Dimension$(S) \leq k$ for some integer $k$.

Are there approximation algorithms or hardness results for this problem?

• The functions seem to play no role in maximizing |S| Feb 22, 2011 at 21:50
• The choice of functions determines the VC-Dimension of S. The problem is to find as large a class of functions as possible, subject to a VC-dimension constraint. Feb 22, 2011 at 22:26
• I see. So translated to "geometry land", you're given a collection of ranges (f acts as a characteristic function) and you want a largest subcollection of bounded VC dimension. Feb 22, 2011 at 23:55
• The other problem in answering the question: how is C presented ? We know that the maximum possible size of $S$ is $O(2^{nk})$ by Sauer's Lemma, and writing down even one function in $C$ requires $n$ bits. Feb 22, 2011 at 23:58
• Right. I'm interested in results in any representational regime. You could image that $C$ is presented as a $2^n\times |C|$ matrix, in which case running time $2^n\times |C|$ would be efficient'' (although not time $2^{n\times k}$, which is what it would take to exhaustively check if all collections of $k$ points were shattered). If any algorithmic results are possible with just black-box query access to the functions in $C$, that would be even better. Feb 23, 2011 at 0:09

Edit: the original problem is $n^{1-\epsilon}$-hard to approximate when $k=1$ where $n$ denotes the number of sets.

The dual of a hypergraph is obtained by exchanging vertices with edges, and preserving incidences. It is easier to understand the problem when we note that a hypergraph has VC-dimension 1 iff its dual is cross-free (for all $P, Q$ in $A$, at least one of $P \cap Q, P \backslash Q, Q \backslash P, (P \cup Q)^c$ is empty).

By duality the original problem (for $k=1$) is equivalent to, given a hypergraph $(V, \mathcal{S})$, find a max-size $U \subseteq V$ with $(U, \{S \cap U \mid S \in \mathcal{S}\})$ cross-free.

In fact, this (dual) problem is very hard even when all sets in $\mathcal{S}$ have size 2: then it is a graph and we are looking for a max-size vertex size whose induced subgraph which does not contain any two-edge path (it's not hard to see this is the only way a crossing pair can arise, assuming the graph has at least 4 vertices). But this property is hereditary and nontrivial and thus we can use a result of Feige and Kogan to show hardness.

The dual problem for $k=1$ (find a maximum-size $S$ such that the dual VC-dimension of $S$ is at most 1) is hard to approximate within $n^{1-\epsilon}$ (in a family with $\Theta(n)$ sets).
The reason for this is that the dual VC-dimension of a family $A$ is 1 iff the following holds: for all $P, Q$ in $A$, at least one of $P \cap Q, P \backslash Q, Q \backslash P, (P \cup Q)^c$ is empty. (I.e. VC-dim=1 is the dual of what is often called crossing-freeness.)
We reduce from independent set to computing the maximum-size cross-free subfamily. Given a graph $G=(V, E)$ construct a hypergraph $H=(X, S)$ where $X = V \uplus E \uplus \{0\}$ for some dummy element $0$. For each vertex $v$ of $G$, we add the following set $T_v$ to $S$: $$\{v\} \cup \{e \mid e \textrm{ is an edge incident to }v\}.$$
It's not hard to show a family $\{T_v\}_{v \in U}$ is crossing-free iff $U$ is independent in $G$.