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 条

[41] On the Parameterized Complexity of Maximum Degree Contraction Problem [J].

Saurabh, Saket ;

Tale, Prafullkumar .

ALGORITHMICA, 2022, 84 (02) :405-435

[42] The parameterized complexity of some minimum label problems [J].

Fellows, Michael R. ;

Guo, Jiong ;

Kanj, Iyad .

JOURNAL OF COMPUTER AND SYSTEM SCIENCES, 2010, 76 (08) :727-740

[43] On the parameterized complexity of computing tree-partitions [J].

Bodlaender, Hans L. ;

Groenland, Carla ;

Jacob, Hugo .

DISCRETE MATHEMATICS AND THEORETICAL COMPUTER SCIENCE, 2024, 26 (03)

[44] A survey of parameterized algorithms and the complexity of edge modification [J].

Crespelle, Christophe ;

Drange, Pal Gronas ;

V. Fomin, Fedor ;

Golovach, Petr .

COMPUTER SCIENCE REVIEW, 2023, 48

[45] Parameterized and approximation complexity of PARTIAL VC DIMENSION [J].

Bazgan, Cristina ;

Foucaud, Florent ;

Sikora, Florian .

THEORETICAL COMPUTER SCIENCE, 2019, 766 :1-15

[46] Parameterized Complexity for Domination Problems on Degenerate Graphs [J].

Golovach, Petr A. ;

Villanger, Yngve .

GRAPH-THEORETIC CONCEPTS IN COMPUTER SCIENCE, 2008, 5344 :195-205

[47] On parameterized complexity of the Multi-MCS problem [J].

Chen, Wenbin ;

Schmidt, Matthew C. ;

Samatova, Nagiza F. .

THEORETICAL COMPUTER SCIENCE, 2009, 410 (21-23) :2024-2032

[48] On the Parameterized Complexity of Dynamic Problems with Connectivity Constraints [J].

Abu-Khzam, Faisal N. ;

Egan, Judith ;

Fellows, Michael R. ;

Rosamond, Frances A. ;

Shaw, Peter .

COMBINATORIAL OPTIMIZATION AND APPLICATIONS (COCOA 2014), 2014, 8881 :625-636

[49] On the Parameterized Complexity and Kernelization of the Workflow Satisfiability Problem [J].

Crampton, Jason ;

Gutin, Gregory ;

Yeo, Anders .

ACM TRANSACTIONS ON INFORMATION AND SYSTEM SECURITY, 2013, 16 (01)

[50] Parameterized Complexity of the Spanning Tree Congestion Problem [J].

Bodlaender, Hans L. ;

Fomin, Fedor V. ;

Golovach, Petr A. ;

Otachi, Yota ;

van Leeuwen, Erik Jan .

ALGORITHMICA, 2012, 64 (01) :85-111

← 1 2 3 4 5 →