The parameterized complexity of regular subgraph problems and generalizations

Luke Mathieson*, Stefan Szeider

*Corresponding author for this work

Research output: Chapter in Book/Report/Conference proceedingConference proceeding contribution

5 Citations (Scopus)

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 languageEnglish
Title of host publicationTheory of Computing 2008 - Proceedings of the Fourteenth Computing: The Australasian Theory Symposium, CATS 2008
EditorsJames Harland, Prabhu Manyem
Pages79-86
Number of pages8
Volume77
Publication statusPublished - 2008
EventTheory of Computing 2008 - 14th Computing: The Australasian Theory Symposium, CATS 2008 - Wollongong, NSW, Australia
Duration: 22 Jan 200825 Jan 2008

Other

OtherTheory of Computing 2008 - 14th Computing: The Australasian Theory Symposium, CATS 2008
CountryAustralia
CityWollongong, NSW
Period22/01/0825/01/08

Keywords

  • Parameterized complexity
  • Regular subgraphs

Fingerprint Dive into the research topics of 'The parameterized complexity of regular subgraph problems and generalizations'. Together they form a unique fingerprint.

Cite this