Résumé
In this paper we study the problem of finding an induced sub-graph of size at most k with minimum degree at least d for a given graph G, from the parameterized complexity perspective. We call this problem MINIMUM SUBGRAPH OF MINIMUM DEGREE >= d (MSMDd). For d = 2 it corresponds to finding a shortest cycle of the graph. Our main motivation to study this problem is its strong relation to DENSE k-SUBGRAPH and TRAFFIC GROOMING problems.
First, we show that MSMSd is fixed-parameter intractable (provided FPT not equal W[1]) for d >= 3 in general graphs, by showing it to be W[1]-hard using a reduction from MULTI-COLOR CLIQUE. In the second part of the paper we provide explicit fixed-parameter tractable (FPT) algorithms for the problem in graphs with bounded local tree-width and graphs with excluded minors, faster than those coming from the meta-theorem of Frick and Grohe [13] about problems definable in first order logic over "locally tree-decomposable structures". In particular, this implies faster fixed-parameter tractable algorithms in planar graphs, graphs of bounded genus, and graphs with bounded maximum degree.