Parameterized Complexity of the Sparsest k-Subgraph in Chordal Graphs - LIRMM - Laboratoire d’Informatique, de Robotique et de Microélectronique de Montpellier Accéder directement au contenu
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⟩
159 Consultations
182 Téléchargements

Partager

Gmail Facebook X LinkedIn More