Parameterized Complexity of the Sparsest k-Subgraph in Chordal Graphs - LIRMM - Laboratoire d’Informatique, de Robotique et de Microélectronique de Montpellier
Rapport (Rapport De Recherche) Année : 2013

Parameterized Complexity of the Sparsest k-Subgraph in Chordal Graphs

Résumé

(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).
Fichier principal
Vignette du fichier
researchReport.pdf (741.52 Ko) Télécharger le fichier
Origine Fichiers produits par l'(les) auteur(s)
Loading...

Dates et versions

lirmm-00875132 , version 1 (21-10-2013)

Identifiants

  • HAL Id : lirmm-00875132 , version 1

Citer

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⟩
184 Consultations
204 Téléchargements

Partager

More