On polynomial kernelization for Stable Cutset

A stable cutset in a graph G is a set S V (G) such that vertices of S are pairwise non-adjacent and such that G-S is disconnected, i. e. , it is both stable (or independent) set and a cutset (or separator). Unlike general cutsets, it is NP-complete to determine whether a given graph G has any stable cutset. Recently, Rauch et al. \ FCT 2023 gave a number of fixed-parameter tractable (FPT) algorithms, time f (k) |V (G) |ᶜ, for Stable Cutset under a variety of parameters k such as the size of a (given) dominating set, the size of an odd cycle transversal, or the deletion distance to P₅-free graphs. Earlier works imply FPT algorithms relative to clique-width and relative to solution size. We complement these findings by giving the first results on the existence of polynomial kernelizations for, i. e. , efficient preprocessing algorithms that return an equivalent instance of size polynomial in the parameter value. Under the standard assumption that NP coNP/poly, we show that no polynomial kernelization is possible relative to the deletion distance to a single path, generalizing deletion distance to various graph classes, nor by the size of a (given) dominating set. We also show that under the same assumption no polynomial kernelization is possible relative to solution size, i. e. , given (G, k) answering whether there is a stable cutset of size at most k. On the positive side, we show polynomial kernelizations for parameterization by modulators to a single clique, to a cluster or a co-cluster graph, and by twin cover.