Articulo
On maximizing clique, clique-Helly and hereditary clique-Helly induced subgraphs
Autor
Alcón, Liliana Graciela
Faria, L.
Figueiredo, C. M. H. de
Gutiérrez, Marisa
Institución
Resumen
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, M. Gutierrez, Clique graph recognition is NP-complete, in: Proc. WG 2006, in: 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, 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 frac(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. Facultad de Ciencias Exactas
Ítems relacionados
Mostrando ítems relacionados por Título, autor o materia.
-
Diseño de un sistema P de tejido y un algoritmo molecular para la resolución del problema MAX-CLIQUE
Hugo Armando Guillén Ramírez -
Heurística para el problema MAX-CLIQUE basada en un modelo de cómputo con ADN utilizando GPUs
Nelson Emmanuel Ordóñez Guillén -
On second iterated clique graphs that are also third iterated clique graphs
de Caria, Pablo Jesús; Pizaña, Miguel A. (Elsevier, 2015-12)Iterated clique graphs arise when the clique operator is applied to a graph more than once. Determining whether a graph is a clique graph or an iterated clique graph is usually a difficult task. The fact that being a clique ...