Parameterized complexity of finding small degree-constrained subgraphs - LIRMM - Laboratoire d’Informatique, de Robotique et de Microélectronique de Montpellier
Journal Articles Journal of Discrete Algorithms Year : 2012

Parameterized complexity of finding small degree-constrained subgraphs

Abstract

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].

Dates and versions

lirmm-00736517 , version 1 (28-09-2012)

Identifiers

Cite

Omid Amini, Ignasi Sau, Saket Saurabh. Parameterized complexity of finding small degree-constrained subgraphs. Journal of Discrete Algorithms, 2012, 10, pp.70-83. ⟨10.1016/j.jda.2011.05.001⟩. ⟨lirmm-00736517⟩
132 View
0 Download

Altmetric

Share

More