Parameterized algorithms for recognizing monopolar and 2-subcolorable graphs
Files
Publication date
2018-03
Authors
Kanj, Iyad A.
Komusiewicz, Christian
Sorge, Manuel
van Leeuwen, Erik Jan
Editors
Advisors
Supervisors
Document Type
Article
Metadata
Show full item recordCollections
License
taverne
Abstract
A graph G is a (A, B )-graph if V (G) can be bipartitioned into A and B such that G[A] satisfies property A and G[B] satisfies property B . The (A, B )-Recognition problem is to recognize whether a given graph is a (A, B )-graph. There are many (A, B )-Recognition problems, including the recognition problems for bipartite, split,and unipolar graphs. We present efficient algorithms for many cases of (A, B )-Recognitionbased on a technique which we dub inductive recognition. In particular, we givefixed-parameter algorithms for two NP-hard (A, B )-Recognition problems, Monopolar Recognition and 2-Subcoloring, parameterized by the number of maximal cliques in G[A]. We complement our algorithmic results with several hardness results for (A, B )-Recognition.
Keywords
Vertex-partition problems, Graph classes, Monopolar graphs, Subcolorings, Split graphs, Unipolar graphs, Fixed-parameter algorithms, Taverne
Citation
Kanj, I A, Komusiewicz, C, Sorge, M & van Leeuwen, E J 2018, 'Parameterized algorithms for recognizing monopolar and 2-subcolorable graphs', Journal of Computer and System Sciences, vol. 92, pp. 22-47. https://doi.org/10.1016/j.jcss.2017.08.002