  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$. The task is to find a hitting set
for $\mathcal{F}$ that minimizes the maximum number of elements in any of the
sets of $\mathcal{B}$. Our focus is on determining the complexity of some
special cases of Sparse-HS with respect to the sparseness $k$, which is the
optimum number of hitting set elements in any set of $\mathcal{B}$.
  For the Sparse Vertex Cover (Sparse-VC) problem, $V$ is given by the vertex
set of a graph, and $\mathcal{F}$ is its edge set. We prove NP-hardness for
sparseness $k\geq 2$ and polynomial time solvability for $k=1$. We also provide
a polynomial-time $2$-approximation for any $k$. A special case of Sparse-VC is
Fair Vertex Cover (Fair-VC), where the family $\mathcal{B}$ is given by vertex
neighbourhoods. For this problem we prove NP-hardness for constant $k$ and
provide a polynomial-time $(2-\frac{1}{k})$-approximation. This is better than
any approximation possible for Sparse-VC or Vertex Cover (under UGC).
  We then consider two problems derived from Sparse-HS related to the highway
dimension, a graph parameter modelling transportation networks. Most algorithms
for graphs of low highway dimension compute solutions to the $r$-Shortest Path
Cover ($r$-SPC) problem, where $r>0$, $\mathcal{F}$ contains all shortest paths
of length between $r$ and $2r$, and $\mathcal{B}$ contains all balls of radius
$2r$. There is an XP algorithm that computes solutions to $r$-SPC of sparseness
at most $h$ if the input graph has highway dimension $h$, but the existence if
an FPT algorithm was open. We prove that $r$-SPC and also the related
$r$-Highway Dimension ($r$-HD) problem are both W[1]-hard. Furthermore, we
prove that $r$-SPC admits a polynomial-time $O(\log n)$-approximation.
