Exploring Minimal Blocking Sets for Kernelization Lower Bounds for F-Minor Deletion

Zusammenfassung

For Vertex Cover, a minimal blocking set of a graph G is an inclusion-wise minimal vertex set contained in no minimum vertex cover of G. Bougeret et al. [SIDMA 2022] showed that, for all minor-closed graph classes ????, Vertex Cover has a polynomial kernel parameterized by the distance to ???? if and only if ???? has bounded minimal blocking sets.1 1 We assume ????????⊈????????????????/???????????????? throughout the abstract and introduction. In this work, we explore how far this connection between minimal blocking sets and kernelization extends to ℱ-Minor Deletion parameterized by the deletion distance to ????. For a fixed nonempty finite family ℱ of graphs, given a graph G and integer k, ℱ-Minor Deletion asks whether G can be made free of minors from ℱ by deleting at most k vertices. A minimal ℱ-blocking set of G is an inclusion-wise minimal vertex set not contained in any optimal ℱ-Minor Deletion solution of G. For families ℱ of connected graphs, we show that if some graph class ???? closed under disjoint union has unbounded minimal ℱ-blocking sets, then ℱ-Minor Deletion parameterized by the deletion distance to ???? has no polynomial kernel. This generalizes a result of Hols et al. [SIDMA 2022] for Vertex Cover. We then show that this criterion does not capture all kernelization lower bounds for ℱ-Minor Deletion, even for minor-closed graph classes. Motivated by the work of Dekker and Jansen [Discrete Appl. Math. 2024], we study the more general notion of extended ℱ-blocking sets. Under additional conditions, we show that ???? having unbounded minimal extended ℱ-blocking sets rules out polynomial kernels. For every fixed integer η≥1, Pw-η Deletion is the problem of deleting at most k vertices to reduce the pathwidth of a given graph to at most η. We show that it has no polynomial kernel parameterized by the distance to graphs with pathwidth at most η+1. Moreover, for all families ℱ of graphs, each connected and having at least two vertices, we show that ℱ-Minor Deletion parameterized by the distance to graphs with pathwidth at most maxF∈ℱ⁡pw⁡(F)+1 has no polynomial kernel. These lower bounds rely in part on a pathwidth analysis of a minor modification of a construction due to Donkers and Jansen [J. Comput. Syst. Sci. 2021].