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.