HAL will be down for maintenance from Friday, June 10 at 4pm through Monday, June 13 at 9am. More information
Skip to Main content Skip to Navigation
Reports

Parameterized Complexity of the Smallest Degree Constraint Subgraph Problem

Omid Amini 1 Ignasi Sau Valls 1 Saket Saurabh 2
1 MASCOTTE - Algorithms, simulation, combinatorics and optimization for telecommunications
CRISAM - Inria Sophia Antipolis - Méditerranée , Laboratoire I3S - 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.
Complete list of metadata

Cited literature [1 references]  Display  Hide  Download

https://hal.inria.fr/inria-00157970
Contributor : Rapport de Recherche Inria Connect in order to contact the contributor
Submitted on : Tuesday, July 3, 2007 - 5:37:23 PM
Last modification on : Friday, February 4, 2022 - 3:11:29 AM
Long-term archiving on: : Friday, September 24, 2010 - 11:00:09 AM

Files

RR-6237.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : inria-00157970, version 4

Citation

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

Share

Metrics

Record views

251

Files downloads

212