## Abstract

We study variants and generalizations of the problem of finding an r-regular subgraph (where r ≥ 3) in a given graph by deleting at most k vertices. Moser and Thilikos (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.

Original language | English |
---|---|

Title of host publication | Theory of Computing 2008 - Proceedings of the Fourteenth Computing: The Australasian Theory Symposium, CATS 2008 |

Editors | James Harland, Prabhu Manyem |

Pages | 79-86 |

Number of pages | 8 |

Volume | 77 |

Publication status | Published - 2008 |

Event | Theory of Computing 2008 - 14th Computing: The Australasian Theory Symposium, CATS 2008 - Wollongong, NSW, Australia Duration: 22 Jan 2008 → 25 Jan 2008 |

### Other

Other | Theory of Computing 2008 - 14th Computing: The Australasian Theory Symposium, CATS 2008 |
---|---|

Country | Australia |

City | Wollongong, NSW |

Period | 22/01/08 → 25/01/08 |

## Keywords

- Parameterized complexity
- Regular subgraphs