Algorithms for finding clique-transversals of graphs

Abstract

A clique-transversal of a graph $G$ is a subset of verticesintersecting all the cliques of $G$. It is NP-hard to determinethe minimum cardinality $au_c$ of a clique-transversal of $G$.In this work, first we propose an algorithm for determining thisparameter for a general graph, which runs in polynomial time, forfixed $au_c$. This algorithm is employed for finding the minimumcardina-lity clique-transversal of $overline{3K_2}$-freecircular-arc graphs in $O(n^4)$ time. Further we describe analgorithm for determining $au_c$ of a Helly circular-arc graphin $O(n)$ time. This represents an improvement over an existingalgorithm by Guruswami and Pandu Rangan which requires $O(n^2)$time. Finally, the last proposed algorithm is modified, so as tosolve the weighted version of the corresponding problem, in$O(n^2)$ time.