Parameterized Complexity of the Smallest Degree Constraint Subgraph Problem - Inria - Institut national de recherche en sciences et technologies du numérique Accéder directement au contenu
Rapport (Rapport De Recherche) Année : 2007

Parameterized Complexity of the Smallest Degree Constraint Subgraph Problem

Résumé

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.
Fichier principal
Vignette du fichier
RR-DegreeFPT.pdf (350.33 Ko) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)

Dates et versions

inria-00157970 , version 1 (27-06-2007)
inria-00157970 , version 2 (28-06-2007)
inria-00157970 , version 3 (03-07-2007)
inria-00157970 , version 4 (03-07-2007)

Identifiants

  • HAL Id : inria-00157970 , version 2

Citer

Omid Amini, Ignasi Sau, Saket Saurabh. Parameterized Complexity of the Smallest Degree Constraint Subgraph Problem. [Research Report] 2007. ⟨inria-00157970v2⟩
268 Consultations
253 Téléchargements

Partager

Gmail Facebook X LinkedIn More