Skip to Main content Skip to Navigation

The k-Sparsest Subgraph Problem

Rémi Watrigant 1, * Marin Bougeret 1 Rodolphe Giroudeau 1 
* Corresponding author
1 MAORE - Methods, Algorithms for Operations REsearch
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 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).
Complete list of metadata

Cited literature [16 references]  Display  Hide  Download
Contributor : Rémi Watrigant Connect in order to contact the contributor
Submitted on : Friday, January 18, 2013 - 9:45:51 AM
Last modification on : Friday, August 5, 2022 - 3:03:01 PM
Long-term archiving on: : Saturday, April 1, 2017 - 6:57:32 AM


Files produced by the author(s)


  • HAL Id : lirmm-00735713, version 2



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



Record views


Files downloads