Algorithms for finding clique-transversals of graphs

DURAN, GUILLERMO ALFREDO; LIN, MIN CHIH; MERA, SERGIO; SZWARCFITER, JAYME

ANNALS OF OPERATIONS RESEARCH

SPRINGER

Año: 2008 vol. 157 p. 37 - 45

0254-5330

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.