Solving Partition Problems Almost Always Requires Pushing Many Vertices Around

A fundamental graph problem is to recognize whether the vertex set of a graph G can be bipartitioned into sets A and B such that G[A] and G[B] satisfy properties ΠA and ΠB, respectively.
This so-called (ΠA, ΠB)-Recognition problem generalizes amongst others the recognition of
3-colorable, bipartite, split, and monopolar graphs. A powerful algorithmic technique that can
be used to obtain fixed-parameter algorithms for many cases of (ΠA, ΠB)-Recognition, as well
as several other problems, is the pushing process. For bipartition problems, the process starts
with an “almost correct” bipartition (A0
, B0
), and pushes appropriate vertices from A0
to B0 and
vice versa to eventually arrive at a correct bipartition.
In this paper, we study whether (ΠA, ΠB)-Recognition problems for which the pushing
process yields fixed-parameter algorithms also admit polynomial problem kernels. In our study,
we focus on the first level above triviality, where ΠA is the set of P3-free graphs (disjoint unions
of cliques, or cluster graphs), the parameter is the number of clusters in the cluster graph G[A],
and ΠB is characterized by a set H of connected forbidden induced subgraphs. We prove that,
under the assumption that NP 6⊆ coNP/poly, (ΠA, ΠB)-Recognition admits a polynomial kernel
if and only if H contains a graph of order at most 2. In both the kernelization and the lower
bound results, we make crucial use of the pushing process.