Solving Partition Problems Almost Always Requires Pushing Many Vertices Around

Iyad A. Kanj, Christian Komusiewicz, Manuel Sorge, Erik Jan van Leeuwen

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review


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.
Original languageEnglish
Title of host publication26th Annual European Symposium on Algorithms
Subtitle of host publicationESA 2018, August 20-22, 2018, Helsinki, Finland
EditorsYossi Azar, Hannah Bast, Grzegorz Herman
Place of PublicationSaarbrücken
PublisherSchloss Dagstuhl – Leibniz-Zentrum für Informatik GmbH
Number of pages14
ISBN (Electronic)978-3-95977-081-1
Publication statusPublished - 2018

Publication series



Dive into the research topics of 'Solving Partition Problems Almost Always Requires Pushing Many Vertices Around'. Together they form a unique fingerprint.

Cite this