Parameterized Complexity of the Sparsest k-Subgraph in Chordal Graphs

Rémi Watrigant 1 Nicolas Bousquet 2 Marin Bougeret 1 Rodolphe Giroudeau 1
1 MAORE - Méthodes Algorithmes pour l'Ordonnancement et les Réseaux
LIRMM - Laboratoire d'Informatique de Robotique et de Microélectronique de Montpellier
2 ALGCO - Algorithmes, Graphes et Combinatoire
LIRMM - Laboratoire d'Informatique de Robotique et de Microélectronique de Montpellier
Abstract : (This is the long version of the paper accepted to SOFSEM 2014) In this paper we study the Sparsest k-Subgraph problem which consists in finding a subset of k vertices in a graph which induces the minimum number of edges. The Sparsest k-Subgraph problem is a natural generalization of the Independent Set problem, and thus is NP-hard (and even W[1]-hard) in general graphs. In this paper we investigate the parameterized complexity of both Sparsest k-Subgraph and Densest k-Subgraph in chordal graphs. We first provide simple proofs that Densest k-Subgraph in chordal graphs is FPT and does not admit a polynomial kernel unless NP ⊆ coNP/poly (both parameterized by k). More involved proofs will ensure the same behavior for Sparsest k- Subgraph in the same graph class. We lastly provide an FPT algorithm in interval graphs for Sparsest k-Subgraph, but parameterized by the number of edges of the solution (a stronger parameterization than by k).
Type de document :
Rapport
[Research Report] RR-13033, LIRMM. 2013
Liste complète des métadonnées

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

https://hal-lirmm.ccsd.cnrs.fr/lirmm-00875132
Contributeur : Rémi Watrigant <>
Soumis le : lundi 21 octobre 2013 - 11:29:44
Dernière modification le : jeudi 11 janvier 2018 - 06:26:15
Document(s) archivé(s) le : vendredi 7 avril 2017 - 13:29:01

Fichier

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

Identifiants

  • HAL Id : lirmm-00875132, version 1

Collections

Citation

Rémi Watrigant, Nicolas Bousquet, Marin Bougeret, Rodolphe Giroudeau. Parameterized Complexity of the Sparsest k-Subgraph in Chordal Graphs. [Research Report] RR-13033, LIRMM. 2013. 〈lirmm-00875132〉

Partager

Métriques

Consultations de la notice

147

Téléchargements de fichiers

165