Skip to Main content Skip to Navigation
Reports

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).
Complete list of metadatas

Cited literature [17 references]  Display  Hide  Download

https://hal-lirmm.ccsd.cnrs.fr/lirmm-00875132
Contributor : Rémi Watrigant <>
Submitted on : Monday, October 21, 2013 - 11:29:44 AM
Last modification on : Thursday, June 11, 2020 - 8:56:02 PM
Document(s) archivé(s) le : Friday, April 7, 2017 - 1:29:01 PM

File

researchReport.pdf
Files produced by the author(s)

Identifiers

  • 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⟩

Share

Metrics

Record views

243

Files downloads

355