Special Issue on Selected Papers from the Sixth International Workshop on Algorithms and Computation, WALCOM 2012
Parameterized Algorithms for (r,l)-Partization
Vol. 17, no. 2, pp. 129-146, 2013. Regular paper.
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*(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.
Submitted: April 2012.
Reviewed: July 2012.
Revised: August 2012.
Accepted: December 2012.
Final: December 2012.
Published: January 2013.
Communicated by Shin-ichi Nakano
article (PDF)