Parameterized Algorithms for (r,l)-Partization
R. Krithika, N. S. Narayanaswamy · Journal of Graph Algorithms and Applications · 2013
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*(2k) 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.