Kanj, Iyad ;
Komusiewicz, Christian ;
Sorge, Manuel ;
Jan van Leeuwen, Erik
Parameterized Algorithms for Recognizing Monopolar and 2Subcolorable Graphs
Abstract
We consider the recognition problem for two graph classes that generalize split and unipolar graphs, respectively.
First, we consider the recognizability of graphs that admit a monopolar partition: a partition of the vertex set into sets A,B such that G[A] is a disjoint union of cliques and G[B] an independent set. If in such a partition G[A] is a single clique, then G is a split graph. We show that in
O(2^k * k^3 * (V(G) + E(G))) time we can decide whether G admits a monopolar partition
(A,B) where G[A] has at most k cliques. This generalizes the lineartime algorithm for recognizing split graphs corresponding to the case when k=1.
Second, we consider the recognizability of graphs that admit a 2subcoloring: a partition of the vertex set into sets A,B such that each of G[A] and G[B] is a disjoint union of cliques. If in such a partition G[A] is a single clique, then G is a unipolar graph. We show that in
O(k^(2k+2) * (V(G)^2+V(G) * E(G))) time we can decide whether G admits a
2subcoloring (A,B) where G[A] has at most k cliques. This generalizes the polynomialtime algorithm for recognizing unipolar graphs corresponding to the case when k=1.
We also show that in O(4^k) time we can decide whether G admits a 2subcoloring (A,B) where G[A] and G[B] have at most k cliques in total.
To obtain the first two results above, we formalize a technique, which we dub inductive recognition, that can
be viewed as an adaptation of iterative compression to recognition problems. We believe that the formalization
of this technique will prove useful in general for designing parameterized algorithms for recognition problems.
Finally, we show that, unless the Exponential Time Hypothesis fails, no subexponentialtime algorithms for the
above recognition problems exist, and that, unless P=NP, no generic fixedparameter algorithm exists for the
recognizability of graphs whose vertex set can be bipartitioned such that one part is a disjoint union of k
cliques.
BibTeX  Entry
@InProceedings{kanj_et_al:LIPIcs:2016:6036,
author = {Iyad Kanj and Christian Komusiewicz and Manuel Sorge and Erik Jan van Leeuwen},
title = {{Parameterized Algorithms for Recognizing Monopolar and 2Subcolorable Graphs}},
booktitle = {15th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2016)},
pages = {14:114:14},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959770118},
ISSN = {18688969},
year = {2016},
volume = {53},
editor = {Rasmus Pagh},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2016/6036},
URN = {urn:nbn:de:0030drops60360},
doi = {10.4230/LIPIcs.SWAT.2016.14},
annote = {Keywords: vertexpartition problems, monopolar graphs, subcolorings, split graphs, unipolar graphs, fixedparameter algorithms}
}
22.06.2016
Keywords: 

vertexpartition problems, monopolar graphs, subcolorings, split graphs, unipolar graphs, fixedparameter algorithms 
Seminar: 

15th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2016)

Issue date: 

2016 
Date of publication: 

22.06.2016 