06044016

a

06044016 Krithika, R. Narayanaswamy, N.S. Generalized above guarantee vertex cover and $r$-partization. Rahman, Md. Saidur (ed.) et al., WALCOM: Algorithms and computation. 6th international workshop, WALCOM 2012, Dhaka, Bangladesh, February 15--17, 2012. Proceedings. Berlin: Springer (ISBN 978-3-642-28075-7/pbk). Lecture Notes in Computer Science 7157, 17-27 (2012). 2012 Berlin: Springer EN Parameterized complexity Generalized above guarantee vertex cover Odd cycle transversal $r$-Partization Perfect graphs Split graphs

doi:10.1007/978-3-642-28076-4_5

Summary: Vertex cover and odd cycle transversal are minimum cardinality sets of vertices of a graph whose deletion makes the resultant graph 1-colorable and 2-colorable, respectively. As a natural generalization of these well-studied problems, we consider the Graph r-Partization problem of finding a minimum cardinality set of vertices whose deletion makes the graph $r$-colorable. We explore further connections to Vertex Cover by introducing Generalized Above Guarantee Vertex Cover, a variant of Vertex Cover defined as: Given a graph $G$, a clique cover $\cal K$ of $G$ and a non-negative integer $k$, does $G$ have a vertex cover of size at most $k+\sum_{C \in \cal K}(|C|-1)$? We study the parameterized complexity hardness of this problem by a reduction from $r$-Partization. We then describe sequacious fixed-parameter tractability results for $r$-Partization, parameterized by the solution size $k$ and the required chromaticity $r$, in perfect graphs and split graphs. For Odd Cycle Transversal, we describe an $O ^{*}(2^{k })$ algorithm for perfect graphs and a polynomial-time algorithm for co-chordal graphs.