Parameterized and Approximation Complexity of Partial VC Dimension

Abstract

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$ such that the set $\{e\cap C,e\in E\}$ of distinct hyperedge-intersections with $C$ has size at least $\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 $\ell =2^k$, and of Distinguishing Transversal, which corresponds to the case $\ell =|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.

24 pages, 2 figures

References in corpus (4)

• Identification, location-domination and metric dimension on interval and permutation graphs. II. Algorithms and complexity
• Identification, location-domination and metric dimension on interval and permutation graphs. I. Bounds
• Identifying codes in hereditary classes of graphs and VC-dimension
• Hitting Set for hypergraphs of low VC-dimension

Cited by in corpus (2)

• Neighbourhood complexity of graphs of bounded twin-width
• Complexity and Approximation for Discriminating and Identifying Code Problems in Geometric Setups