Skip to Main content Skip to Navigation
Reports

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.
Complete list of metadatas

Cited literature [11 references]  Display  Hide  Download

https://hal-lirmm.ccsd.cnrs.fr/lirmm-00744655
Contributor : Rémi Watrigant <>
Submitted on : Friday, June 7, 2013 - 10:37:00 AM
Last modification on : Thursday, June 11, 2020 - 8:56:02 PM
Document(s) archivé(s) le : Tuesday, April 4, 2017 - 6:04:13 PM

File

reduction.pdf
Files produced by the author(s)

Identifiers

  • 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⟩

Share

Metrics

Record views

188

Files downloads

649