Parameterized complexity of finding regular induced subgraphs

Hannes Moser, Dimitrios M. Thilikos

Research output: Contribution to journalArticlepeer-review


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 languageEnglish (US)
Pages (from-to)181-190
Number of pages10
JournalJournal of Discrete Algorithms
Issue number2
StatePublished - Jun 2009


  • Parameterized algorithm
  • Problem kernelization
  • Vertex deletion problem

ASJC Scopus subject areas

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


Dive into the research topics of 'Parameterized complexity of finding regular induced subgraphs'. Together they form a unique fingerprint.

Cite this