Skip to Main content Skip to Navigation
Reports

The k-Sparsest Subgraph Problem

Rémi Watrigant 1, * Marin Bougeret 1 Rodolphe Giroudeau 1
* Corresponding author
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 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 metadatas

Cited literature [16 references]  Display  Hide  Download

https://hal-lirmm.ccsd.cnrs.fr/lirmm-00735713
Contributor : Rémi Watrigant <>
Submitted on : Friday, January 18, 2013 - 9:45:51 AM
Last modification on : Thursday, June 11, 2020 - 8:56:02 PM
Long-term archiving on: : Saturday, April 1, 2017 - 6:57:32 AM

File

RR.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : lirmm-00735713, version 2

Collections

Citation

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

Share

Metrics

Record views

329

Files downloads

533