Algorithmic aspects of clique-transversal and clique-independent sets

A minimum clique-transversal set MCT(G) of a graph G = (V,E) is a set S sub set of or equal to V of minimum cardinality that meets all maximal cliques in G. A maximum clique-independent set MCI(G) of G is a set of maximum numb er of pairwise vertex-disjoint maximal cliques. We prove that the problem o f finding an MCT(G) and an MCI(G) is NP-hard for cocompatability, planar, l ine and total graphs. As an interesting corollary we obtain that the proble m of finding a minimum number of elements of a poset to meet all maximal an tichains of the poset remains NP-hard even if the poset has height two, the reby generalizing a result of Duffas et al. (J. Combin. Theory Ser. A 58 (1 991) 158-164). We present a polynomial algorithm for the above problems on Helly circular-are graphs which is the first such algorithm for a class of graphs that is not clique-perfect. We also present polynomial algorithms fo r the weighted version of the clique-transversal problem on strongly chorda l graphs, chordal graphs of bounded clique size, and cographs. The algorith ms presented run in linear time for strongly chordal graphs and cographs. T hese mark the first attempts at the weighted version of the problem. (C) 20 00 Elsevier Science B.V. All rights reserved.