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: Current Trends in Theory and Practice of Computer Science, Jan 2014, High Tatras, Slovakia. 40th International Conference on Current Trends in Theory and Practice of Computer Science, Nový Smokovec, Slovakia, January 26-29, 2014, Proceedings, 8327, pp.150-161, 2014, LNCS. 〈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 : mercredi 18 juillet 2018 - 11:52:05

Identifiants

Collections

Citation

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

Partager

Métriques

Consultations de la notice

120