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, M. Gutierrez, Clique graph recognition is NP-complete, in: Proc. WG 2006, in: Lecture N...

Descripción completa

Detalles Bibliográficos
Autores principales: Alcón, Liliana Graciela, Faria, L., Figueiredo, C. M. H. de, Gutiérrez, Marisa
Formato: Articulo
Lenguaje:Inglés
Publicado: 2010
Materias:
Matemática
Approximation algorithms
Clique graphs
Clique-Helly graphs
Hereditary clique-Helly graphs
Max SNP-hard
NP-complete
Acceso en línea:http://sedici.unlp.edu.ar/handle/10915/82445
Aporte de:
SEDICI (UNLP) de Universidad Nacional de La Plata
id I19-R120-10915-82445
record_format dspace
institution Universidad Nacional de La Plata
institution_str I-19
repository_str R-120
collection SEDICI (UNLP)
language Inglés
topic Matemática
Approximation algorithms
Clique graphs
Clique-Helly graphs
Hereditary clique-Helly graphs
Max SNP-hard
NP-complete
Clique graphs
spellingShingle Matemática
Approximation algorithms
Clique graphs
Clique-Helly graphs
Hereditary clique-Helly graphs
Max SNP-hard
NP-complete
Clique graphs
Alcón, Liliana Graciela
Faria, L.
Figueiredo, C. M. H. de
Gutiérrez, Marisa
On maximizing clique, clique-Helly and hereditary clique-Helly induced subgraphs
topic_facet Matemática
Approximation algorithms
Clique graphs
Clique-Helly graphs
Hereditary clique-Helly graphs
Max SNP-hard
NP-complete
Clique graphs
description 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.
format Articulo
Articulo
author Alcón, Liliana Graciela
Faria, L.
Figueiredo, C. M. H. de
Gutiérrez, Marisa
author_facet Alcón, Liliana Graciela
Faria, L.
Figueiredo, C. M. H. de
Gutiérrez, Marisa
author_sort Alcón, Liliana Graciela
title On maximizing clique, clique-Helly and hereditary clique-Helly induced subgraphs
title_short On maximizing clique, clique-Helly and hereditary clique-Helly induced subgraphs
title_full On maximizing clique, clique-Helly and hereditary clique-Helly induced subgraphs
title_fullStr On maximizing clique, clique-Helly and hereditary clique-Helly induced subgraphs
title_full_unstemmed On maximizing clique, clique-Helly and hereditary clique-Helly induced subgraphs
title_sort on maximizing clique, clique-helly and hereditary clique-helly induced subgraphs
publishDate 2010
url http://sedici.unlp.edu.ar/handle/10915/82445
work_keys_str_mv AT alconlilianagraciela onmaximizingcliquecliquehellyandhereditarycliquehellyinducedsubgraphs
AT farial onmaximizingcliquecliquehellyandhereditarycliquehellyinducedsubgraphs
AT figueiredocmhde onmaximizingcliquecliquehellyandhereditarycliquehellyinducedsubgraphs
AT gutierrezmarisa onmaximizingcliquecliquehellyandhereditarycliquehellyinducedsubgraphs
bdutipo_str Repositorios
_version_ 1764820488288206849

Ejemplares similares