Parameterized complexity of finding small degree-constrained subgraphs

2 ALGCO - Algorithmes, Graphes et Combinatoire
LIRMM - Laboratoire d'Informatique de Robotique et de Microélectronique de Montpellier
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].
Keywords :
Type de document :
Article dans une revue
Journal of Discrete Algorithms, Elsevier, 2012, 10, pp.70-83. 〈10.1016/j.jda.2011.05.001〉
Liste complète des métadonnées

https://hal-lirmm.ccsd.cnrs.fr/lirmm-00736517
Contributeur : Ignasi Sau <>
Soumis le : vendredi 28 septembre 2012 - 12:54:27
Dernière modification le : jeudi 24 mai 2018 - 15:59:22

Citation

Omid Amini, Ignasi Sau, 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〉

Métriques

Consultations de la notice