On Parameterized Exponential Time Complexity

被引：0
|
作者：
Chen, Jianer [1 ]
Kanj, Iyad A. [2 ]
Ge Xia [3 ]
机构：
[1] Texas A&M Univ, Dept Comp Sci & Engn, College Stn, TX 77843 USA
[2] Depaul Univ, Sch CTI, Chicago, IL 60604 USA
[3] Lafayette Coll, Dept Comp Sci, Easton, PA 18042 USA
来源：
THEORY AND APPLICATIONS OF MODELS OF COMPUTATION | 2009年 / 5532卷
关键词：
LOWER BOUNDS; ALGORITHMS;
D O I：
暂无
中图分类号：
TP301 [理论、方法];
学科分类号：
081202 ;
摘要：
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(root 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.
引用
收藏
页码：168 / +
页数：2
相关论文
共 50 条
  • [1] On parameterized exponential time complexity
    Chen, Jianer
    Kanj, Iyad A.
    Xia, Ge
    THEORETICAL COMPUTER SCIENCE, 2009, 410 (27-29) : 2641 - 2648
  • [2] Parameterized complexity: exponential speed-up for planar graph problems
    Alber, J
    Fernau, H
    Niedermeier, R
    JOURNAL OF ALGORITHMS-COGNITION INFORMATICS AND LOGIC, 2004, 52 (01): : 26 - 56
  • [3] Parameterized complexity: Exponential speed-up for planar graph problems
    Alber, J
    Fernau, H
    Niedermeier, R
    AUTOMATA LANGUAGES AND PROGRAMMING, PROCEEDING, 2001, 2076 : 261 - 272
  • [4] Polynomial time approximation schemes and parameterized complexity
    Chen, Jianer
    Huang, Xiuzhen
    Kanj, Iyad A.
    Xia, Ge
    DISCRETE APPLIED MATHEMATICS, 2007, 155 (02) : 180 - 193
  • [5] Polynomial time approximation schemes and parameterized complexity
    Chen, JN
    Huang, XZ
    Kanj, IA
    Xia, G
    MATHEMATICAL FOUNDATIONS OF COMPUTER SCIENCE 2004, PROCEEDINGS, 2004, 3153 : 500 - 512
  • [6] Parameterized complexity and subexponential-time computability
    Chen, J. (chen@cs.tamu.edu), 1600, Springer Verlag (7370):
  • [7] Parameterized Inapproximability Hypothesis under Exponential Time Hypothesis
    Guruswami, Venkatesan
    Lin, Bingkai
    Ren, Xuandi
    Sun, Yican
    Wu, Kewen
    PROCEEDINGS OF THE 56TH ANNUAL ACM SYMPOSIUM ON THEORY OF COMPUTING, STOC 2024, 2024, : 24 - 35
  • [8] An Exponential Time Parameterized Algorithm for Planar Disjoint Paths
    Lokshtanov, Daniel
    Misra, Pranabendu
    Pilipczuk, Michal
    Saurabh, Saket
    Zehavi, Meirav
    PROCEEDINGS OF THE 52ND ANNUAL ACM SIGACT SYMPOSIUM ON THEORY OF COMPUTING (STOC '20), 2020, : 1307 - 1316
  • [9] Solving Connectivity Problems Parameterized by Treewidth in Single Exponential Time
    Cygan, Marek
    Nederlof, Jesper
    Pilipczuk, Marcin
    Pilipczuk, Michal
    Van Rooij, Johan M. M.
    Wojtaszczyk, Jakub Onufry
    ACM TRANSACTIONS ON ALGORITHMS, 2022, 18 (02)
  • [10] Exponential Time Complexity of the Permanent and the Tutte Polynomial
    Dell, Holger
    Husfeldt, Thore
    Marx, Daniel
    Taslaman, Nina
    Wahlen, Martin
    ACM TRANSACTIONS ON ALGORITHMS, 2014, 10 (04)
12345