NP-hardness of the Sparsest k-Subgraph Problem in Chordal Graphs - LIRMM - Laboratoire d’Informatique, de Robotique et de Microélectronique de Montpellier Accéder directement au contenu
Rapport Année : 2012

NP-hardness of the Sparsest k-Subgraph Problem in Chordal Graphs

Résumé

Given a simple undirected graph G = (V,E) and an integer k ≤ |V|, the k-sparsest subgraph problem asks for a set of k vertices which induce the minimum number of edges. Whereas its special case independent set and many other optimization problems become polynomial-time solvable in chordal graphs, we show that k-sparsest subgraph remains NP-hard in this graph class.
Fichier principal
Vignette du fichier
reduction.pdf (627.11 Ko) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)
Loading...

Dates et versions

lirmm-00744655 , version 1 (23-10-2012)
lirmm-00744655 , version 2 (29-05-2013)
lirmm-00744655 , version 3 (07-06-2013)

Identifiants

  • HAL Id : lirmm-00744655 , version 3

Citer

Rémi Watrigant, Marin Bougeret, Rodolphe Giroudeau. NP-hardness of the Sparsest k-Subgraph Problem in Chordal Graphs. RR-12026, 2012. ⟨lirmm-00744655v3⟩
104 Consultations
302 Téléchargements

Partager

Gmail Facebook X LinkedIn More