Résumé
A blocking set in a graph $G$ is a subset of vertices that intersects every maximum independent set of $G$.Let 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 $F$. Indeed, it turns out that the existence of a polynomial kernel for this problem is closely related to the property that $mmbs(F) = sup_{G∈F}mmbs(G)$ is bounded by a constant, and thus several recent results focused on determining $mmbs(F)$ for different classes $F$. Weconsider the parameterized complexity of computing 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 mmbs and mmhs, which is the size of a maximumminimal hitting set of a hypergraph, a closely related parameter. Finally, we consider the problem of computing mmbs parameterized by treewidth, especially relevant in the context of kernelization. Given the “counting” nature of 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.