On approximability of optimization problems related to Red/Blue-split graphs

Abstract

An edge-bicolored graph G=(V,RB) is called Red/Blue-split graph if there exists a partition IB and IR of V such that IB and IR are independent sets in (V,B) and (V,R), respectively. Red/Blue-split graphs generalize several well studied graph classes including split graphs, bipartite graphs and KnigEgervry graphs. In this paper we consider the algorithmic complexity of various optimization problems like minimum edge (or vertex) deletion and maximum edge (or vertex) induced subgraph related to Red/Blue split graphs. All these problems are NP-hard and thus we look at them from algorithmic paradigms that are meant for coping with NP-hardness. We obtain various hardness as well as algorithmic results for these problems in the realm of approximation algorithms and parameterized complexity. The main tool we use to obtain all our results is polynomial time transformations between appropriate problems. On the way, we also resolve some problems related to inapproximability about certain optimization problems mentioned by Korach et al. (2006) [17].