Abstract

Title: A note on sub-exponential time parameterized complexity
Published: April 2003
Authors: Jianer Chen, Iyad A. 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: [postscript, pdf]