On maximizing clique, clique-Helly and hereditary clique-Helly induced subgraphs

Clique-Helly and hereditary clique-Helly graphs are polynomial-time recognizable. Recently, we presented a proof that the clique graph recognition problem is NP-complete [L. Alcón, L. Faria, C. M. H. de Figueiredo and M. Gutierrez. Clique graph recognition is NP-complete. In Proc. WG 2006, Lecture Notes in Comput. Sci., vol. 4271, Springer, 2006, pp. 269–277]. In this work, we consider the decision problems: given a graph G = ( V , E ) and an integer k ≥ 0 , we ask whether there exists a subset V ′ ⊆ V with | V ′ | ≥ k , such that the induced subgraph G [ V ′ ] of G is, respectively, a clique, clique-Helly or hereditary clique-Helly graph. The first problem is clearly NP-complete from [L. Alcón, L. Faria, C. M. H. de Figueiredo and M. Gutierrez. Clique graph recognition is NP-complete. In Proc. WG 2006, Lecture Notes in Comput. Sci., vol. 4271, Springer, 2006, pp. 269–277]; we prove that the other two mentioned decision problems are NP-complete, even for maximum degree 6 planar graphs. We consider the corresponding maximization problems of finding a maximum induced subgraph that is, respectively, clique, clique-Helly or hereditary clique-Helly. We show that these problems are Max SNP-hard, even for maximum degree 6 graphs. We generalize these results for other graph classes. We exhibit a polynomial 6-approximation algorithm to minimize the number of vertices to be removed in order to obtain a hereditary clique-Helly subgraph.