Title: |
A note on parameterized
exponential time complexity |

Authors: |
Jianer Chen, Iyad Kanj, and Ge Xia |

Abstract: |
In this paper we define the notion of an f(k)-uniform parameterized
exponential time scheme. We show that a problem can be
solved in parameterized O(2 time if and only if it
has an ^{o(f(k))}p(n))f(k)-uniform parameterized exponential time scheme (p
is a polynomial). We then illustrate how our
formulation can be used to show that special instances of parameterized NP-hard
problems are as difficult as the general
instances. For example, we show that the Planar
Dominating Set problem on degree-3 graphs can be solved in O(2
parameterized time if and only if the general Planar
Dominating Set problem can. Apart from their
complexity theoretic implications, our results have some interesting algorithmic
implications as^{o(√k)}p(n))well. |

Full Paper: |
[ps, pdf] |