Approximability of Clique Transversal in Perfect Graphs

作者：Fiorini Samuel; Krithika R^*; Narayanaswamy N S; Raman Venkatesh

来源：Algorithmica, 2018, 80(8): 2221-2239.

DOI：10.1007/s00453-017-0315-3

• r-Clique transversal
• Odd cycle transversal
• Perfect graphs
• Approximation algorithms
• Linear programming

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+1/2-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.

• 出版日期2018-8