## 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 Π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.

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.

Original language | English |
---|---|

Title of host publication | 26th Annual European Symposium on Algorithms |

Subtitle of host publication | ESA 2018, August 20-22, 2018, Helsinki, Finland |

Editors | Yossi Azar, Hannah Bast, Grzegorz Herman |

Place of Publication | Saarbrücken |

Publisher | Schloss Dagstuhl – Leibniz-Zentrum für Informatik GmbH |

Number of pages | 14 |

ISBN (Electronic) | 978-3-95977-081-1 |

DOIs | |

Publication status | Published - 2018 |

### Publication series

Name | LIPICS |
---|---|

Volume | 112 |