Please use this identifier to cite or link to this item: http://hdl.handle.net/1959.13/43088
- Title
- Parameterized approximation of dominating set problems
- Author/Creator
-
Downey, Rodney G.;
Fellows, Michael R.;
McCartin, Catherine;
Rosamond, Frances
- Institution
- The University of Newcastle. Research Division, Office of the Deputy Vice-Chancellor (Research)
- Description
- A problem open for many years is whether there is an FPT algorithm that given a graph G and parameter k, either: (1) determines that G has no k-Dominating Set, or (2) produces a dominating set of size at most g(k), where g(k) is some fixed function of k. Such an outcome is termed an FPT approximation algorithm. We describe some results that begin to provide some answers. We show that there is no such FPT algorithm for g(k) of the form k+c (where c is a fixed constant, termed an additive FPT approximation), unless FPT = W[2]. We answer the analogous problem completely for the related Independent Dominating Set (IDS) problem, showing that IDS does not admit an FPT approximation algorithm, for any g(k), unless FPT = W[2].
- Relation
- Information Processing Letters Vol. 109, Issue 1, p. 68-70
- Publisher Link
- http://dx.doi.org/10.1016/j.ipl.2008.09.017
- Date
- 2008
- Publisher
- Elsevier
- Keyword(s)
-
parameterized complexity;
FPT approximation;
approximation algorithms
- Resource Type
- journal article
- Identifier
- http://hdl.handle.net/1959.13/43088
- Identifier
- ISSN:0020-0190
- Reviewed
39 Visitors
40 Hits
0 Downloads
