The Parameterized Complexity of Regular Subgraph Problems and Generalizations

Mathieson, L. and Szeider, S.

    We study variants and generalizations of the problem of finding an r-regular subgraph (where r \ge 3) in a given graph by deleting at most k vertices. Moser and Thilikos have shown that the problem is fixed-parameter tractable (FPT) if parameterized by (k, r). They asked whether the problem remains fixed-parameter tractable if parameterized by k alone. We answer this question negatively: we show that if parameterized by k alone the problem is W[1]-hard and therefore very unlikely fixed-parameter tractable. We also give W[1]-hardness results for variants of the problem where the parameter is the number of vertex and edge deletions allowed, and for a new generalized form of the problem where the obtained subgraph is not necessarily regular but its vertices have certain prescribed degrees. Following this we demonstrate fixed-parameter tractability for the considered problems if the parameter includes the regularity r or an upper bound on the prescribed degrees in the generalized form of the problem. These FPT results are obtained via kernelization, so also provide a practical approach to the problems presented.
Cite as: Mathieson, L. and Szeider, S. (2008). The Parameterized Complexity of Regular Subgraph Problems and Generalizations. In Proc. Fourteenth Computing: The Australasian Theory Symposium (CATS 2008), Wollongong, NSW, Australia. CRPIT, 77. Harland, J. and Manyem, P., Eds. ACS. 79-86.
pdf (from crpit.com) pdf (local if available) BibTeX EndNote GS