On parameterized exponential time complexity Academic Article

abstract

• 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 2o (sqrt(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. 2009 Elsevier B.V. All rights reserved.

authors

• Chen, Jianer

published proceedings

• THEORETICAL COMPUTER SCIENCE

author list (cited authors)

• Chen, J., Kanj, I. A., & Xia, G. e.

citation count

• 5

complete list of authors

• Chen, Jianer||Kanj, Iyad A||Xia, Ge

publication date

• June 2009

publisher

• Elsevier  Publisher

published in

• Theoretical Computer Science  Journal

keywords

• Exact Algorithms
• Parameterized Algorithms
• Parameterized Complexity
• Subexponential Time Complexity

Digital Object Identifier (DOI)

• 10.1016/j.tcs.2009.03.006

start page

• 2641

end page

• 2648

volume

• 410

issue

• 27-29

URL

• http%3A%2F%2Fdx.doi.org%2F10.1016%2Fj.tcs.2009.03.006