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-hard
and therefore very unlikely fixed-parameter tractable.
We also give W-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. |
(local if available)