Advertisement
Published in:
2009 | OriginalPaper | Chapter
On Parameterized Exponential Time Complexity
Authors : Jianer Chen, Iyad A. Kanj, Ge Xia
Published in: Theory and Applications of Models of Computation
Publisher: Springer Berlin Heidelberg
Activate our intelligent search to find suitable subject content or patents.
Select sections of text to find matching patents with Artificial Intelligence. powered by
Select sections of text to find additional relevant content using AI-assisted search. powered by
In this paper, we show that special instances of parameterized NP-hard problems are as difficult as the general instances in terms of their subexponential time computability. For example, we show that the
Planar Dominating Set
problem on degree-3 graphs can be solved in
$2^{o(\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.