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(2o(f(k))p(n)) time if and only if it has an 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(2o(√k)p(n)) 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.
Full Paper:	[ps, pdf]