Parameterized complexity of finding small degree-constrained subgraphs

In this article we study the parameterized complexity of problems consisting in finding degree-constrained subgraphs, taking as the parameter the number of vertices of the desired subgraph. Namely, given two positive integers d and k, we study the problem of finding a d-regular (induced or not) subgraph with at most k vertices and the problem of finding a subgraph with at most k vertices and of minimum degree at least d. The latter problem is a natural parameterization of the d-girth of a graph (the minimum order of an induced subgraph of minimum degree at least d). We first show that both problems are fixed-parameter intractable in general graphs. More precisely, we prove that the first problem is W[1]-hard using a reduction from Multi-Color Clique. The hardness of the second problem (for the non-induced case) follows from an easy extension of an already known result. We then provide explicit fixed-parameter tractable (FPT) algorithms to solve these problems in graphs with bounded local treewidth and graphs with excluded minors, using a dynamic programming approach. Although these problems can be easily defined in first-order logic, hence by the results of Frick and Grohe (2001) [23] are FPT in graphs with bounded local treewidth and graphs with excluded minors, the dependence on k of our algorithms is considerably better than the one following from Frick and Grohe (2001) [23].