# Parameterized and Approximation Complexity of Partial VC Dimension

arXiv: https://arxiv.org/abs/1609.05110 · HTML: https://mlsanity.com/paper/1609.05110/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 16 Sep 2016.

## Built on by (most cited first, 1 of 1)

- [The Parameterized Complexity of Computing the VC-Dimension](https://mlsanity.com/paper/2510.17451/) (2025)

## Abstract (arXiv)

We introduce the problem Partial VC Dimension that asks, given a hypergraph H=(X,E) and integers k and ℓ, whether one can select a set Csubseteq X of k vertices of H such that the set ecap C, e∈ E of distinct hyperedge-intersections with C has size at least ℓ. The sets ecap C define equivalence classes over E. Partial VC Dimension is a generalization of VC Dimension, which corresponds to the case ℓ=2k, and of Distinguishing Transversal, which corresponds to the case ℓ=|E| (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.