Parameterized Complexity of the Sparsest k-Subgraph in Chordal Graphs - LIRMM - Laboratoire d’Informatique, de Robotique et de Microélectronique de Montpellier
Reports (Research Report) Year : 2013

Parameterized Complexity of the Sparsest k-Subgraph in Chordal Graphs

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).
Fichier principal
Vignette du fichier
researchReport.pdf (741.52 Ko) Télécharger le fichier
Origin Files produced by the author(s)
Loading...

Dates and versions

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

Identifiers

  • HAL Id : lirmm-00875132 , version 1

Cite

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⟩
166 View
189 Download

Share

More