NP-hardness of k-sparsest subgraph in Chordal Graphs - LIRMM - Laboratoire d’Informatique, de Robotique et de Microélectronique de Montpellier Access content directly
Reports Year : 2012

NP-hardness of k-sparsest subgraph 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 (643.45 Ko) Télécharger le fichier
Origin Files produced by the author(s)

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 1

Cite

Rémi Watrigant, Marin Bougeret, Rodolphe Giroudeau. NP-hardness of k-sparsest subgraph in Chordal Graphs. RR-12026, 2012. ⟨lirmm-00744655v1⟩
140 View
387 Download

Share

Gmail Mastodon Facebook X LinkedIn More