Solving Partition Problems Almost Always Requires Pushing Many Vertices Around

A fundamental graph problem is to recognize whether the vertex set of a graph 𝐺
can be bipartitioned into sets 𝐴
and 𝐵
such that 𝐺⁡[𝐴]
and 𝐺⁡[𝐵]
satisfy properties Π𝐴
and Π𝐵
, respectively. This so-called (Π𝐴,Π𝐵)
-Recognition problem generalizes, amongst others, the recognition of 3-colorable, bipartite, split, and monopolar graphs. In this paper, we study whether certain fixed-parameter tractable (Π𝐴,Π𝐵)
-Recognition problems admit polynomial kernels. In our study, we focus on the first level above triviality, where Π𝐴
is the set of 𝑃3
-free graphs (disjoint unions of cliques, or cluster graphs), the parameter is the number of clusters in the cluster graph 𝐺⁡[𝐴]
, and Π𝐵
is characterized by a set H
of connected forbidden induced subgraphs. We prove that, under the assumption that 𝑁⁢𝑃⊈𝑐⁢𝑜⁢𝑁⁢𝑃/𝑝⁢𝑜⁢𝑙⁢𝑦
, (Π𝐴,Π𝐵)
-Recognition admits a polynomial kernel if and only if H
contains a graph with at most two vertices. In both the kernelization and the lower bound results, we exploit the properties of a pushing process, which is an algorithmic technique used recently by Heggerness et al. and by Kanj et al. to obtain fixed-parameter algorithms for many cases of (Π𝐴,Π𝐵)
-Recognition, as well as several other problems.