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. Alcn, L. Faria, C.M.H. de Figueiredo, M. Gutierrez, Clique graph recognition is NP-complete, in: Proc. WG 2006, in: Lecture Notes in Comput. Sci., vol. 4271, Springer, 2006, pp. 269277]. In this work, we consider the decision problems: given a graph G=(V,E) G = ( V , E ) and an integer k?0 k ? 0 , we ask whether there exists a subset V??V V ? ? V with |V?|?k | V ? | ? k such that the induced subgraph G[V?] G [ V ? ] of G G is, variously, a clique, clique-Helly or hereditary clique-Helly graph. The first problem is clearly NP-complete, from the above reference; we prove that the other two decision problems mentioned 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 show a general polynomial-time 1 ? + 1 -approximation algorithm for these problems when restricted to graphs with fixed maximum degree ? ? . We generalize these results to 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.
hereditary clique-helly graphs clique-helly graphs clique graphs np-complete max snp-hard approximation algorithms