Parameterized Complexity of the Sparsest k-Subgraph Problem in Chordal Graphs - LIRMM - Laboratoire d’Informatique, de Robotique et de Microélectronique de Montpellier
Conference Papers Year : 2014

Parameterized Complexity of the Sparsest k-Subgraph Problem in Chordal Graphs

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.
No file

Dates and versions

lirmm-01251025 , version 1 (05-01-2016)

Identifiers

Cite

Marin Bougeret, Nicolas Bousquet, Rodolphe Giroudeau, Rémi Watrigant. Parameterized Complexity of the Sparsest k-Subgraph Problem in Chordal Graphs. SOFSEM: Theory and Practice of Computer Science, Jan 2014, Nový Smokovec, Slovakia. pp.150-161, ⟨10.1007/978-3-319-04298-5_14⟩. ⟨lirmm-01251025⟩
175 View
0 Download

Altmetric

Share

More