Parameterized Algorithms for Recognizing Monopolar and 2-Subcolorable Graphs

Abstract

A graph $G$ is a $({\Pi }_A,{\Pi }_B)$-graph if $V(G)$ can be bipartitioned into $A$ and $B$ such that $G[A]$ satisfies property ${\Pi }_A$ and $G[B]$ satisfies property ${\Pi }_B$. The $({\Pi }_A,{\Pi }_B)$-Recognition problem is to recognize whether a given graph is a $({\Pi }_A,{\Pi }_B)$-graph. There are many $({\Pi }_A,{\Pi }_B)$-Recognition problems, including the recognition problems for bipartite, split, and unipolar graphs. We present efficient algorithms for many cases of $({\Pi }_A,{\Pi }_B)$-Recognition based on a technique which we dub inductive recognition. In particular, we give fixed-parameter algorithms for two NP-hard $({\Pi }_A,{\Pi }_B)$-Recognition problems, Monopolar Recognition and 2-Subcoloring. We complement our algorithmic results with several hardness results for $({\Pi }_A,{\Pi }_B)$-Recognition.

A preliminary version of this paper appears in the proceedings of SWAT 2016. A journal version of this paper appears in Journal of Computer and System Sciences, volume 92, 2018. This ArXiv paper additionally discusses relations to the iterative localization technique (Heggernes et al., Information and Computation, 2013)