On Sparse Hitting Sets: from Fair Vertex Cover to Highway Dimension

Johannes Blum, Yann Disser, Andreas Emil Feldmann +2

We consider the Sparse Hitting Set (Sparse-HS) problem, where we are given a set system $(V,\mathcal{F},\mathcal{B})$ with two families $\mathcal{F},\mathcal{B}$ of subsets of $V$.…