NP-hardness of the Sparsest k-Subgraph Problem in Chordal Graphs - LIRMM - Laboratoire d’Informatique, de Robotique et de Microélectronique de Montpellier
Reports Year : 2012

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

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.
Fichier principal
Vignette du fichier
reduction.pdf (627.11 Ko) Télécharger le fichier
Origin Files produced by the author(s)
Loading...

Dates and versions

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

Identifiers

  • HAL Id : lirmm-00744655 , version 3

Cite

Rémi Watrigant, Marin Bougeret, Rodolphe Giroudeau. NP-hardness of the Sparsest k-Subgraph Problem in Chordal Graphs. RR-12026, 2012. ⟨lirmm-00744655v3⟩
160 View
404 Download

Share

More