Parameterized and Approximation Complexity of Partial VC Dimension

Cristina Bazgan, Florent Foucaud, Florian Sikora

We introduce the problem Partial VC Dimension that asks, given a hypergraph $H=(X,E)$ and integers $k$ and $\ell$, whether one can select a set $C\subseteq X$ of $k$ vertices of $H…