Approximability of Clique Transversal in Perfect Graphs

Given an undirected simple graph G, a set of vertices is an r-clique transversal if it has at least one vertex from every r-clique. Such sets generalize vertex covers as a vertex cover is a 2-clique transversal. Perfect graphs are a well-studied class of graphs on which a minimum weight vertex cover can be obtained in polynomial time. Further, an r-clique transversal in a perfect graph is also a set of vertices whose deletion results in an (r- 1) -colorable graph. In this work, we study the problem of finding a minimum weight r-clique transversal in a perfect graph. This problem is known to be NP-hard for r≥ 3 and admits a straightforward r-approximation algorithm. We describe two different r+12-approximation algorithms for the problem. Both the algorithms are based on (different) linear programming relaxations. The first algorithm employs the primal–dual method while the second uses rounding based on a threshold value. We also show that the problem is APX-hard and describe hardness results in the context of parameterized algorithms and kernelization.SCOPUS: ar.j