Parameterized Algorithms for Recognizing Monopolar and 2-Subcolorable Graphs
- Prelegent(ci)
- Erik Jan van Leeuwen
- Termin
- 17 listopada 2016 12:15
- Pokój
- p. 5870
- Seminarium
- Seminarium "Algorytmika"
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.