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].
Document type :
Journal articles
Complete list of metadatas

https://hal-lirmm.ccsd.cnrs.fr/lirmm-00736517
Contributor : Ignasi Sau <>
Submitted on : Friday, September 28, 2012 - 12:54:27 PM
Last modification on : Tuesday, December 17, 2019 - 10:00:03 AM

Links full text

Identifiers

Citation

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

Share

Metrics

Record views

238