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

Rémi Watrigant 1 Marin Bougeret 1 Rodolphe Giroudeau 1
1 MAORE - Méthodes Algorithmes pour l'Ordonnancement et les Réseaux
LIRMM - Laboratoire d'Informatique de Robotique et de Microélectronique de Montpellier
Abstract : 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.
Type de document :
Rapport
RR-12026, 2012
Liste complète des métadonnées

Littérature citée [11 références]  Voir  Masquer  Télécharger

https://hal-lirmm.ccsd.cnrs.fr/lirmm-00744655
Contributeur : Rémi Watrigant <>
Soumis le : vendredi 7 juin 2013 - 10:37:00
Dernière modification le : mercredi 18 juillet 2018 - 11:52:05
Document(s) archivé(s) le : mardi 4 avril 2017 - 18:04:13

Fichier

reduction.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : lirmm-00744655, version 3

Collections

Citation

Rémi Watrigant, Marin Bougeret, Rodolphe Giroudeau. NP-hardness of the Sparsest k-Subgraph Problem in Chordal Graphs. RR-12026, 2012. 〈lirmm-00744655v3〉

Partager

Métriques

Consultations de la notice

147

Téléchargements de fichiers

273