Clique-transversals of Helly circular-arc graphs

GUILLERMO DURÁN; MIN CHIH LIN; SERGIO MERA; JAYME L. SZWARCFITER

La Habana, Cuba

Congreso; XII CLAIO (Congreso Latino Iberoamericano de Investigación de Operaciones); 2004

Universidad de la Habana e Instituto Superior Politécnico José Antonio Echeverría

A circular-arc graph is the intersection graph of arcs of an circle. A Helly circular-arc graph is a circular-arcgraph whose arcs satisfy the Helly property, that is every subset of pairwise intersecting arcs contains acommon point of the circle. Helly circular-arc graphs capture more closely than general circular-arc graphssome relevant properties of interval graphs. A clique-transversal of a graph is a subset of vertices intersectingall the cliques of the graph. It is NP-hard to compute the minimum cardinality of a clique-transversal for ageneral graph. In this work, we describe an algorithm for computing this parameter for Helly circular-arcgraphs. The proposed algorithm has complexity O(n). This represents an improvement over an existingalgorithm, whose complexity is O(n^2). In addition, we consider the weighted version of this problem. Eachvertex is given a non negative real weight and the aim is to find a clique-transversal whose total weight isminimum. We propose an algorithm for the weighted problem which runs in O(n^2) time.