The Parameterized Complexity of Regular Subgraph Problems and GeneralizationsProceedings of CATS 2008, Computing: The Australasian Theory Symposium, University of Wollongong, New South Wales, Australia, January 22-25, 2008, part of the Australasian Computer Society Week (ACSW 2008), CRPIT vol. 77, pp. 79-86, Australian Computer Society, 2008. Abstract:We study variants and generalizations of the problem of finding an r-regular subgraph (where r>2) in a given graph by deleting at most k vertices. Moser and Thilikos (ACiD 2006) 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.Download: [paper pdf] [back to Stefan Szeider's homepage] |