The k-Sparsest Subgraph Problem - LIRMM - Laboratoire d’Informatique, de Robotique et de Microélectronique de Montpellier Access content directly
Reports Year : 2012

The k-Sparsest Subgraph Problem


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 that induce the minimum number of edges. As a generalization of the classical independent set problem, k-sparsest subgraph cannot ad- mit (unless P = NP) neither an approximation nor an FPT algorithm (parameterized by the number of edges in the solution) in all graph classes where independent set is NP-hard. Thus, it appears natural to investigate the approximability and fixed parameterized tractability of k-sparsest subgraph in graph classes where independent set is polynomial, such as subclasses of perfect graphs. In this paper, we first present a simple greedy tight 2-approximation algorithm in proper interval graphs, and then we use dynamic programming to design a PTAS in proper interval graph and an FPT algorithm in interval graphs (parameterized by the number of edges in the solution).
Fichier principal
Vignette du fichier
RR.pdf (640.45 Ko) Télécharger le fichier
Origin : Files produced by the author(s)

Dates and versions

lirmm-00735713 , version 1 (26-09-2012)
lirmm-00735713 , version 2 (18-01-2013)


  • HAL Id : lirmm-00735713 , version 2


Rémi Watrigant, Marin Bougeret, Rodolphe Giroudeau. The k-Sparsest Subgraph Problem. RR-12019, 2012. ⟨lirmm-00735713v2⟩
219 View
589 Download


Gmail Facebook Twitter LinkedIn More