Theoretical Computer Science Stack Exchange is a question and answer site for theoretical computer scientists and researchers in related fields. It only takes a minute to sign up.
Sign up to join this community
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?
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)
