The k-Sparsest Subgraph Problem - LIRMM - Laboratoire d’Informatique, de Robotique et de Microélectronique de Montpellier Accéder directement au contenu
Rapport Année : 2012

The k-Sparsest Subgraph Problem

Résumé

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
Origine : Fichiers produits par l'(les) auteur(s)
Loading...

Dates et versions

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

Identifiants

  • HAL Id : lirmm-00735713 , version 2

Citer

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

Partager

Gmail Facebook X LinkedIn More