Parameterized Algorithms for (r,l)-Partization

Abstract

We consider the (r,l)-Partization problem of finding a set of at most k vertices whose deletion results in a graph that can be partitioned into r independent sets and l cliques. Restricted to perfect graphs and split graphs, we describe sequacious fixed-parameter tractability results for (r,0)-Partization, parameterized by k and r. For (r,l)-Partization where r+l=2, we describe an O^*(2^k) algorithm for perfect graphs. We then study the parameterized complexity hardness of a generalization of the Above Guarantee Vertex Cover by a reduction from (r,l)-Partization