On parameterized exponential time complexity

In this paper we study the notion of parameterized exponential time complexity. We show that a parameterized problem can be solved in parameterized 2o(f(k))p(n) time if and only if it is solvable in time O(2δf(k)q(n)) for any constant δ>0, where p and q are polynomials. We then illustrate how this equivalence 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 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 well.