Parameterized complexity of computing maximum minimal blocking and hitting sets

Júlio Araújo, Marin Bougeret, Victor A. Campos +1

A blocking set in a graph $G$ is a subset of vertices that intersects every maximum independent set of $G$. Let $\mathsf{mmbs}(G)$ be the size of a maximum (inclusion-wise) minimal bl…