The algorithmic complexity of the minus clique-transversal problem

Abstract A minus clique-transversal function of a graph G = ( V , E ) is a function f : V → { - 1 , 0 , 1 } such that ∑ u ∈ V ( C ) f ( u ) ⩾ 1 for every clique C of G . The weight of a minus clique-transversal function is f ( V ) = ∑ f ( v ) , over all vertices v ∈ V . The minus clique-transversal number of a graph G , denoted τ c - ( G ) , equals the minimum weight of a minus clique-transversal function of G . The upper minus clique-transversal number of a graph G , denoted T c - ( G ) , equals the maximum weight of a minimal minus clique-transversal function of G . In this paper, we show that the minus clique-transversal problem (respectively, upper minus clique-transversal problem) is NP-complete even when restricted to chordal graphs. On the other hand, we give a linear algorithm to solve the minus clique-transversal problem for block graphs.