Please use this identifier to cite or link to this item: http://hdl.handle.net/1959.14/138066
11 Visitors
12 Hits
0 Downloads
- Title
- The Parameterized complexity of regular subgraph problems and generalizations
- Related
- Australasian Theory Symposium (14th : 2008) (22 - 25 January 2008 : Wollongong, Australia)
- Related
- Harland, James and Manyem, Prabhu. Theory of computing 2008 : proceedings of the Fourteenth Computing--the Australasian Theory Symposium (CATS 2008), Wollongong, NSW, Australia, January 2008, p.79-86
- Related
- Conferences in research and practice in information technolog 77
- Publisher
- Sydney : Australian Computer Society
- Date
- 2008
- Author/Creator
- Mathieson, Luke
- Author/Creator
- Szeider, Stefan
- Description
- 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.
- Description
- 8 page(s)
- Subject Keyword
- Parameterized Complexity
- Subject Keyword
- Regular Subgraphs
- Resource Type
- conference paper
- Organisation
- Macquarie University. Dept. of Computing
- Identifier
- http://hdl.handle.net/1959.14/138066
- Identifier
- ISBN:9781920682583
- Identifier
- ISSN:1445-1336
- Identifier
- mq_res-ext-201109190806-11
- Language
- eng
- Reviewed
