### Inhalt des Dokuments

# Parameterized Algorithms for Recognizing Monopolar and 2-Subcolorable Graphs

**Manuel
Sorge **(TU
Berlin**)**

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 linear-time algorithm for recognizing split graphs corresponding
to the case when k = 1. Second, we consider the recognizability of
graphs that admit a 2-subcoloring: 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 2-subcoloring (A, B) where G[A] has at most k cliques. This
generalizes the polynomial-time 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 2-subcoloring (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 subexponential-time algorithms for the above recognition problems exist, and that, unless P=NP, no generic fixed-parameter algorithm exists for the recognizability of graphs whose vertex set can be bipartitioned such that one part is a disjoint union of k cliques.

This is a joint work with Iyad Kanj, Christian Komusiewicz, and Erik Jan van Leeuwen.

Date | Speaker | Location | Language |
---|---|---|---|

09.06.2016 16:15 | Manuel
Sorge | TEL
512 | English |

Back to the research colloquium site. [1]

_term_2016/