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?

  • $\begingroup$ The functions seem to play no role in maximizing |S| $\endgroup$ Commented Feb 22, 2011 at 21:50
  • $\begingroup$ 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. $\endgroup$
    – Aaron Roth
    Commented Feb 22, 2011 at 22:26
  • $\begingroup$ 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. $\endgroup$ Commented Feb 22, 2011 at 23:55
  • $\begingroup$ 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. $\endgroup$ Commented Feb 22, 2011 at 23:58
  • 1
    $\begingroup$ 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. $\endgroup$
    – Aaron Roth
    Commented Feb 23, 2011 at 0:09

2 Answers 2


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.

Original reply

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

But for the original (primal) problem, it seems some more thought is required... looks interesting!


Some relevant related work: Estimating the VC-dimension itself (let alone finding a large subcollection with bounded VC-dimension) in your representation is LOGNP-complete (LOGNP is NP restricted to log n bits of nondeterminism). There's also a bit of related work on estimating and approximating VC-dimension when the presentation of the range space is more compact (see the references within as well)


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.