Parameterized and Approximation Complexity of Partial VC Dimension

We introduce the problem Partial VC Dimension that asks, given a hypergraph $H=(X,E)$ and integers $k$ and $\mathrm{\ell }$, whether one can select a set $C\subseteq X$of$k$verticesof$H$suchthattheset${e\cap C, e\in E}$ of distinct hyperedge-intersections with $C$ has size at least $\mathrm{\ell }$. The sets $e\cap C$ define equivalence classes over $E$. Partial VC Dimension is a generalization of VC Dimension, which corresponds to the case $\mathrm{\ell }=2^k$, and of Distinguishing Transversal, which corresponds to the case $\mathrm{\ell }=\mathrm{\mid }E\mathrm{\mid }$ (the latter is also known as Test Cover in the dual hypergraph). We also introduce the associated fixed-cardinality maximization problem Max Partial VC Dimension that aims at maximizing the number of equivalence classes induced by a solution set of $k$ vertices. We study the algorithmic complexity of Partial VC Dimension and Max Partial VC Dimension both on general hypergraphs and on more restricted instances, in particular, neighborhood hypergraphs of graphs.