Parameterized Complexity of the Sparsest k-Subgraph Problem in Chordal Graphs

Marin Bougeret 1 Nicolas Bousquet 2 Rodolphe Giroudeau 1 Rémi Watrigant 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 : 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.
Type de document :
Communication dans un congrès
SOFSEM: Theory and Practice of Computer Science, Jan 2014, Nový Smokovec, Slovakia. 40th International Conference on Current Trends in Theory and Practice of Computer Science, LNCS (8327), pp.150-161, 2014, 〈www.sofsem.sk〉. 〈10.1007/978-3-319-04298-5_14〉
Liste complète des métadonnées

https://hal-lirmm.ccsd.cnrs.fr/lirmm-01251025
Contributeur : Rodolphe Giroudeau <>
Soumis le : mardi 5 janvier 2016 - 15:15:05
Dernière modification le : jeudi 15 novembre 2018 - 21:10:43

Identifiants

Collections

Citation

Marin Bougeret, Nicolas Bousquet, Rodolphe Giroudeau, Rémi Watrigant. Parameterized Complexity of the Sparsest k-Subgraph Problem in Chordal Graphs. SOFSEM: Theory and Practice of Computer Science, Jan 2014, Nový Smokovec, Slovakia. 40th International Conference on Current Trends in Theory and Practice of Computer Science, LNCS (8327), pp.150-161, 2014, 〈www.sofsem.sk〉. 〈10.1007/978-3-319-04298-5_14〉. 〈lirmm-01251025〉

Partager

Métriques

Consultations de la notice

131