  A blocking set in a graph $G$ is a subset of vertices that intersects every
maximum independent set of $G$. Let ${\sf mmbs}(G)$ be the size of a maximum
(inclusion-wise) minimal blocking set of $G$. This parameter has recently
played an important role in the kernelization of Vertex Cover parameterized by
the distance to a graph class ${\cal F}$. Indeed, it turns out that the
existence of a polynomial kernel for this problem is closely related to the
property that ${\sf mmbs}({\cal F})=\sup_{G \in {\cal F}}{\sf mmbs}(G)$ is
bounded by a constant, and thus several recent results focused on determining
${\sf mmbs}({\cal F})$ for different classes ${\cal F}$. We consider the
parameterized complexity of computing ${\sf mmbs}$ under various
parameterizations, such as the size of a maximum independent set of the input
graph and the natural parameter. We provide a panorama of the complexity of
computing both ${\sf mmbs}$ and ${\sf mmhs}$, which is the size of a maximum
minimal hitting set of a hypergraph, a closely related parameter. Finally, we
consider the problem of computing ${\sf mmbs}$ parameterized by treewidth,
especially relevant in the context of kernelization. Given the "counting"
nature of ${\sf mmbs}$, it does not seem to be expressible in monadic
second-order logic, hence its tractability does not follow from Courcelle's
theorem. Our main technical contribution is a fixed-parameter tractable
algorithm for this problem.
