LP Approaches to Improved Approximation for Clique Transversal in Perfect Graphs

摘要

Given an undirected simple graph G, a subset T of vertices is an r-clique transversal if it has at least one vertex from every r-clique in G. I.e. T is an r-clique transversal if G - S is K_r-free. r-clique transversals generalize vertex covers as a vertex cover is a set of vertices whose deletion results in a graph that is K_2-free. Perfect graphs are a well-studied class of graphs on which a minimum vertex cover can be obtained in polynomial time. However, the problem of finding a minimum r-clique transversal is NP-hard even for r = 3. As any induced odd length cycle in a perfect graph is a triangle, a triangle-free perfect graph is bipartite. I.e. in perfect graphs, a 3-clique transversal is an odd cycle transversal. In this work, we describe an (r+1/2)-approximation algorithm for r-clique transversal on weighted perfect graphs improving on the straightforward r-approximation algorithm. We then show that 3-CLIQUE TRANSVERSAL is APX-hard on perfect graphs and it is NP-hard to approximate it within any constant factor better than 4/3 assuming the unique games conjecture. We also show intractability results in the parameterized complexity framework.