Parameterized Complexity of the Smallest Degree Constraint Subgraph Problem

Omid Amini 1 Ignasi Sau 1 Saket Saurabh 2
1 MASCOTTE - Algorithms, simulation, combinatorics and optimization for telecommunications
CRISAM - Inria Sophia Antipolis - Méditerranée , COMRED - COMmunications, Réseaux, systèmes Embarqués et Distribués
Abstract : In this paper we initiate the study of finding an induced subgraph of size at most $k$ with minimum degree at least $d$. We call this problem {\sc Minimum Subgraph of Minimum Degree $_{\geq d}$ (MSMD$_d$)}. For $d=2$, it corresponds to finding a shortest cycle of the graph. The problem is strongly related to the \textsc{Dense $k$-Subgraph} problem and is of interest in practical applications. We show that the {\sc MSMS}$_d$ is fixed parameter intractable for $d\geq 3$ in general graphs by showing it to be W[1]-hard by a reduction from {\sc Multi-Color Clique}. On the algorithmic side, we show that the problem is fixed parameter tractable in graphs which excluded minors and graphs with bounded local tree-width. In particular, this implies that the problem is fixed parameter tractable in planar graphs, graphs of bounded genus and graphs with bounded maximum degree.
Type de document :
Rapport
[Research Report] RR-6237, INRIA. 2007, pp.20
Liste complète des métadonnées

Littérature citée [1 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/inria-00157970
Contributeur : Rapport de Recherche Inria <>
Soumis le : mardi 3 juillet 2007 - 17:37:23
Dernière modification le : mercredi 31 janvier 2018 - 10:24:04
Document(s) archivé(s) le : vendredi 24 septembre 2010 - 11:00:09

Fichiers

RR-6237.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : inria-00157970, version 4

Citation

Omid Amini, Ignasi Sau, Saket Saurabh. Parameterized Complexity of the Smallest Degree Constraint Subgraph Problem. [Research Report] RR-6237, INRIA. 2007, pp.20. 〈inria-00157970v4〉

Partager

Métriques

Consultations de la notice

368

Téléchargements de fichiers

157