Kanj, Iyad ;
Komusiewicz, Christian ;
Sorge, Manuel ;
van Leeuwen, Erik Jan
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 socalled (Pi_A,Pi_B)Recognition problem generalizes amongst others the recognition of 3colorable, bipartite, split, and monopolar graphs. A powerful algorithmic technique that can be used to obtain fixedparameter algorithms for many cases of (Pi_A,Pi_B)Recognition, as well as several other problems, is the pushing process. For bipartition problems, the process starts with an "almost correct" bipartition (A',B'), and pushes appropriate vertices from A' to B' and vice versa to eventually arrive at a correct bipartition.
In this paper, we study whether (Pi_A,Pi_B)Recognition problems for which the pushing process yields fixedparameter algorithms also admit polynomial problem kernels. In our study, we focus on the first level above triviality, where Pi_A is the set of P_3free 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 H of connected forbidden induced subgraphs. We prove that, under the assumption that NP not subseteq coNP/poly, (Pi_A,Pi_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.
BibTeX  Entry
@InProceedings{kanj_et_al:LIPIcs:2018:9514,
author = {Iyad Kanj and Christian Komusiewicz and Manuel Sorge and Erik Jan van Leeuwen},
title = {{Solving Partition Problems Almost Always Requires Pushing Many Vertices Around}},
booktitle = {26th Annual European Symposium on Algorithms (ESA 2018)},
pages = {51:151:14},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959770811},
ISSN = {18688969},
year = {2018},
volume = {112},
editor = {Yossi Azar and Hannah Bast and Grzegorz Herman},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2018/9514},
URN = {urn:nbn:de:0030drops95140},
doi = {10.4230/LIPIcs.ESA.2018.51},
annote = {Keywords: Fixedparameter algorithms, Kernelization, Vertexpartition problems, Reduction rules, Crosscomposition}
}
2018
Keywords: 

Fixedparameter algorithms, Kernelization, Vertexpartition problems, Reduction rules, Crosscomposition 
Seminar: 

26th Annual European Symposium on Algorithms (ESA 2018)

Issue date: 

2018 
Date of publication: 

2018 