On the existence of subexponential parameterized algorithms

被引:82
作者
Cai, LM
Juedes, D [1 ]
机构
[1] Ohio Univ, Sch Elect Engn & Comp Sci, Athens, OH 45701 USA
[2] Univ Georgia, Dept Comp Sci, Athens, GA 30602 USA
基金
美国国家科学基金会;
关键词
D O I
10.1016/S0022-0000(03)00074-6
中图分类号
TP3 [计算技术、计算机技术];
学科分类号
0812 ;
摘要
The existence of subexponential-time parameterized algorithms is examined for various parameterized problems solvable in time O(2(O(k))p(n)). It is shown that for each tgreater than or equal to1, there are parameterized problems in FPT for which the existence of O(2(o(k))p(n))-time parameterized algorithms implies the collapse of W[t] to FPT. Evidence is demonstrated that Max-SNP-hard optimization problems do not admit sub-exponential-time parameterized algorithms. In particular, it is shown that each Max-SNP-complete problem is solvable in time O(2(o(k))p(n)) if and only if 3-SATepsilonDTIME(2(o(n))). These results are also applied to show evidence for the non-existence of O(2(o(rootk))p(n))-time parameterized algorithms for a number of other important problems such as Dominating Set, Vertex Cover, and Independent Set on planar graph instances. (C) 2003 Elsevier Science (USA). All rights reserved.
引用
收藏
页码:789 / 807
页数:19
相关论文
共 23 条
[1]   FIXED-PARAMETER TRACTABILITY AND COMPLETENESS .4. ON COMPLETENESS FOR W[P] AND PSPACE ANALOGS [J].
ABRAHAMSON, KA ;
DOWNEY, RG ;
FELLOWS, MR .
ANNALS OF PURE AND APPLIED LOGIC, 1995, 73 (03) :235-276
[2]   Faster exact algorithms for hard problems: A parameterized point of view [J].
Alber, J ;
Gramm, J ;
Niedermeier, R .
DISCRETE MATHEMATICS, 2001, 229 (1-3) :3-27
[3]  
Alber J, 2001, LECT NOTES COMPUT SC, V2076, P261
[4]  
Alber J, 2000, LECT NOTES COMPUT SC, V1851, P97
[5]  
[Anonymous], DIMACS SERIES DISCRE
[6]  
[Anonymous], FEASIBLE MATH
[7]   An improved fixed-parameter algorithm for vertex cover [J].
Balasubramanian, R ;
Fellows, MR ;
Raman, V .
INFORMATION PROCESSING LETTERS, 1998, 65 (03) :163-168
[8]   THE COMPLEXITY OF DECISION VERSUS SEARCH [J].
BELLARE, M ;
GOLDWASSER, S .
SIAM JOURNAL ON COMPUTING, 1994, 23 (01) :97-119
[9]   NONDETERMINISM WITHIN P [J].
BUSS, JF ;
GOLDSMITH, J .
SIAM JOURNAL ON COMPUTING, 1993, 22 (03) :560-572
[10]  
CAI L, 2001, P 28 INT C AUT LANG, P273