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.