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 2 o ( 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 2 o ( 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.

Authors

• Jianer Chen
• Iyad A. Kanj
• Ge Xia

Keywords

• Parameterized complexity
• Subexponential time complexity
• Parameterized algorithms
• Exact algorithms