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

<p>The <em>dual</em> 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).</p>

<p>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.</p>

<p>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 <em>not</em> 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 <em>hereditary</em> and <em>nontrivial</em> and thus we can use a <a href="http://research.microsoft.com/en-us/um/redmond/groups/theory/feige/homepagefiles/hereditary.pdf" rel="noreferrer">result of Feige and Kogan</a> to show hardness.</p>

<p><strong>Original reply</strong></p>

<p>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).</p>

<p>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.)</p>

<p>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\}.$$ </p>

<p>It's not hard to show a family $\{T_v\}_{v \in U}$ is crossing-free iff $U$ is independent in $G$.</p>

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

CC BY-SA 2.5
2011-02-24T14:28:43.430Z
2011-02-28T13:13:04.323Z
2011-02-28T13:13:04.323Z
daveagp
<p>Some relevant related work: Estimating the VC-dimension itself (let alone finding a large subcollection with bounded VC-dimension) in your representation <a href="http://www.sciencedirect.com/science?_ob=ArticleURL&amp;_udi=B6WJ0-45S96GY-3&amp;_user=10&amp;_coverDate=10%2F31%2F1996&amp;_rdoc=1&amp;_fmt=high&amp;_orig=search&amp;_origin=search&amp;_sort=d&amp;_docanchor=&amp;view=c&amp;_searchStrId=1652477992&amp;_rerunOrigin=google&amp;_acct=C000050221&amp;_version=1&amp;_urlVersion=0&amp;_userid=10&amp;md5=9400d7c7dafa2d2dda272e937a832bc9&amp;searchtype=a" rel="noreferrer">is LOGNP-complete</a> (LOGNP is NP restricted to log n bits of nondeterminism). There's also a bit of related work on <a href="http://www.cs.caltech.edu/~umans/papers/MU01.ps" rel="noreferrer">estimating and approximating VC-dimension</a> when the presentation of the range space is more compact (see the references within as well)</p>

CC BY-SA 2.5
2011-02-23T07:02:57.653Z
2011-02-23T07:02:57.653Z
Suresh Venkat
<p>What is known about the following problem?</p>

<blockquote>
  <p>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$.</p>
</blockquote>

<p>Are there approximation algorithms or hardness results for this problem?</p>

CC BY-SA 2.5
2011-02-22T21:50:33.267Z
The functions seem to play no role in maximizing |S|
Suresh Venkat
CC BY-SA 2.5
2011-02-22T22:26:38.247Z
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.
Aaron Roth
CC BY-SA 2.5
2011-02-22T23:55:16.193Z
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.
Suresh Venkat
CC BY-SA 2.5
2011-02-22T23:58:37.313Z
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.
Suresh Venkat
CC BY-SA 2.5
2011-02-23T00:09:01.037Z
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.
Aaron Roth
<reference-request><approximation-algorithms><cg.comp-geom><lg.learning><vc-dimension>
Estimating VC-Dimension
Aaron Roth
# Estimating VC-Dimension

(Asked by: username_0 on 2011-02-22)

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?

**Tags:** reference-request, approximation-algorithms, cg.comp-geom, lg.learning, vc-dimension
> **Comments:**
> **username_1**: The functions seem to play no role in maximizing |S|  
> **username_0**: 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.  
> **username_1**: 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.  
> **username_1**: 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.  
> **username_0**: 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.  

---

## 2 answers

### Answer by username_2 on 2011-02-24. Score: 8 | Accepted answer

**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](http://research.microsoft.com/en-us/um/redmond/groups/theory/feige/homepagefiles/hereditary.pdf) 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!


---

### Answer by username_1 on 2011-02-23. Score: 5

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](http://www.sciencedirect.com/science?_ob=ArticleURL&_udi=B6WJ0-45S96GY-3&_user=10&_coverDate=10%2F31%2F1996&_rdoc=1&_fmt=high&_orig=search&_origin=search&_sort=d&_docanchor=&view=c&_searchStrId=1652477992&_rerunOrigin=google&_acct=C000050221&_version=1&_urlVersion=0&_userid=10&md5=9400d7c7dafa2d2dda272e937a832bc9&searchtype=a) (LOGNP is NP restricted to log n bits of nondeterminism). There's also a bit of related work on [estimating and approximating VC-dimension](http://www.cs.caltech.edu/~umans/papers/MU01.ps) when the presentation of the range space is more compact (see the references within as well)


---

