## Abstract

The r-Regular Induced Subgraph problem asks, given a graph G and a non-negative integer k, whether G contains an r-regular induced subgraph of size at least k, that is, an induced subgraph in which every vertex has degree exactly r. In this paper we examine its parameterization k-Size r-Regular Induced Subgraph with k as parameter and prove that it is W [1]-hard. We also examine the parameterized complexity of the dual parameterized problem, namely, the k-Almost r-Regular Graph problem, which asks for a given graph G and a non-negative integer k whether G can be made r-regular by deleting at most k vertices. For this problem, we prove the existence of a problem kernel of size O (k r (r + k)^{2}).

Original language | English (US) |
---|---|

Pages (from-to) | 181-190 |

Number of pages | 10 |

Journal | Journal of Discrete Algorithms |

Volume | 7 |

Issue number | 2 |

DOIs | |

State | Published - Jun 2009 |

## Keywords

- Parameterized algorithm
- Problem kernelization
- Vertex deletion problem

## ASJC Scopus subject areas

- Theoretical Computer Science
- Discrete Mathematics and Combinatorics
- Computational Theory and Mathematics