Selection of a group of representatives satisfying certain fairness constraints, is a commonly occurring scenario. Motivated by this, we initiate a systematic algorithmic study of a \emph{ fair} version of \textsc{ Hitting Set}. In the classical \textsc{ Hitting Set} problem, the input is a universe $\mathcal{ U}$, a family $\mathcal{ F}$ of subsets of $\mathcal{ U}$, and a non-negative integer $k$. The goal is to determine whether there exists a subset $S \subseteq \mathcal{ U}$ of size $k$ that \emph{ hits} (i.e., intersects) every set in $\mathcal{ F}$. Inspired by several recent works, we formulate a fair version of this problem, as follows. The input additionally contains a family $\mathcal{ B}$ of subsets of $\mathcal{ U}$, where each subset in $\mathcal{ B}$ can be thought of as the group of elements of the same \emph{ type}. We want to find a set $S \subseteq \mathcal{ U}$ of size $k$ that (i) hits all sets of $\mathcal{ F}$, and (ii) does not contain \emph{ too many} elements of each type. We call this problem \textsc{ Fair Hitting Set}, and chart out its tractability boundary from both classical as well as multivariate perspective. Our results use a multitude of techniques from parameterized complexity including classical to advanced tools, such as, methods of representative sets for matroids, FO model checking, and a generalization of best known kernels for \textsc{ Hitting Set}.
Categories: cs.DS