Solving Partition Problems Almost Always Requires Pushing Many Vertices Around

Abstract

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 ${\Pi }_A$ and ${\Pi }_B$, respectively. This so-called $({\Pi }_A,{\Pi }_B)$-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 $({\Pi }_A,{\Pi }_B)$-Recognition problems admit polynomial kernels. In our study, we focus on the first level above triviality, where ${\Pi }_A$ is the set of $P_3$-free graphs (disjoint unions of cliques, or cluster graphs), the parameter is the number of clusters in the cluster graph $G[A]$, and ${\Pi }_B$ is characterized by a set $\mathcal{H}$ of connected forbidden induced subgraphs. We prove that, under the assumption that NP is not a subset of coNP/poly, \textsc{$({\Pi }_A,{\Pi }_B)$-Recognition} admits a polynomial kernel if and only if $\mathcal{H}$ contains a graph with at most $2$ 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 $({\Pi }_A,{\Pi }_B)$-Recognition, as well as several other problems.

Full version of the corresponding article in the Proceedings of the 26th Annual European Symposium on Algorithms (ESA '18), 35 pages, 7 figures