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 and subexponential-time complexity of satisfiability problems and applications
    Kanj, Iyad
    Szeider, Stefan
    THEORETICAL COMPUTER SCIENCE, 2015, 607 : 282 - 295
  • [3] Solving connectivity problems parameterized by treewidth in single exponential time (Extended abstract)
    Cygan, Marek
    Nederlof, Jesper
    Pilipczuk, Marcin
    Pilipczuk, Michal
    van Rooij, Johan M. M.
    Wojtaszczyk, Jakub Onufry
    2011 IEEE 52ND ANNUAL SYMPOSIUM ON FOUNDATIONS OF COMPUTER SCIENCE (FOCS 2011), 2011, : 150 - 159
  • [4] 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)
  • [5] Parameterized and Subexponential-Time Complexity of Satisfiability Problems and Applications
    Kanj, Iyad
    Szeider, Stefan
    COMBINATORIAL OPTIMIZATION AND APPLICATIONS (COCOA 2014), 2014, 8881 : 637 - 651
  • [6] Problems Parameterized by Treewidth Tractable in Single Exponential Time: A Logical Approach
    Pilipczuk, Michal
    MATHEMATICAL FOUNDATIONS OF COMPUTER SCIENCE 2011, 2011, 6907 : 520 - 531
  • [7] Parameterized Complexity of Streaming Diameter and Connectivity Problems
    Oostveen, Jelle J.
    van Leeuwen, Erik Jan
    ALGORITHMICA, 2024, 86 (09) : 2885 - 2928
  • [8] On the Parameterized Complexity of Pooling Design
    Cheng, Yongxi
    Du, Ding-Zhu
    Ko, Ker-I
    Lin, Guohui
    JOURNAL OF COMPUTATIONAL BIOLOGY, 2009, 16 (11) : 1529 - 1537
  • [9] Parameterized Complexity of Paired Domination
    Andreev, Nikita
    Bliznets, Ivan
    Kundu, Madhumita
    Saurabh, Saket
    Tripathi, Vikash
    Verma, Shaily
    COMBINATORIAL ALGORITHMS, IWOCA 2024, 2024, 14764 : 523 - 536
  • [10] On the Parameterized Complexity of Belief Revision
    Pfandler, Andreas
    Ruemmele, Stefan
    Wallner, Johannes Peter
    Woltran, Stefan
    PROCEEDINGS OF THE TWENTY-FOURTH INTERNATIONAL JOINT CONFERENCE ON ARTIFICIAL INTELLIGENCE (IJCAI), 2015, : 3149 - 3155
12345