The k-Sparsest Subgraph Problem

Rémi Watrigant 1, * Marin Bougeret 1 Rodolphe Giroudeau 1
* Auteur correspondant
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).
Type de document :
Rapport
RR-12019, 2012
Liste complète des métadonnées

Littérature citée [16 références]  Voir  Masquer  Télécharger

https://hal-lirmm.ccsd.cnrs.fr/lirmm-00735713
Contributeur : Rémi Watrigant <>
Soumis le : vendredi 18 janvier 2013 - 09:45:51
Dernière modification le : jeudi 11 janvier 2018 - 02:03:54
Document(s) archivé(s) le : samedi 1 avril 2017 - 06:57:32

Fichier

RR.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • 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〉

Partager

Métriques

Consultations de la notice

198

Téléchargements de fichiers

231