FIXED-PARAMETER TRACTABILITY AND COMPLETENESS .1. BASIC RESULTS

作     者：DOWNEY, RG FELLOWS, MR 

作者机构：UNIV VICTORIA DEPT COMP SCI VICTORIA BC V8W 3P6 CANADA 

出 版 物：《SIAM JOURNAL ON COMPUTING》 (工业与应用数学会计算杂志)

年 卷 期：1995年第24卷第4期

页      面：873-921页

核心收录：

学科分类：07[理学] 070104[理学-应用数学] 0701[理学-数学] 0812[工学-计算机科学与技术（可授工学、理学学位）] 

主　　题：FIXED-PARAMETER TRACTABLE W-HIERARCHY PARAMETERIZED COMPLEXITY DOMINATING SET T-NORMALIZED SATISFIABILITY 

摘      要：For many fixed-parameter problems that are trivially soluable in polynomial time, such as (k-)DOMINATING SET, essentially no better algorithm is presently known than the one which tries all possible solutions. Other problems, such as (k-)FEEDBACK VERTEX SET, exhibit fixed-parameter tractability: for each fixed k the problem is soluable in time bounded by a polynomial of degree c, where c is a constant independent of k. We establish the main results of a completeness program which addresses the apparent fixed-parameter intractability of many parameterized problems. In particular, we define a hierarchy of classes of parameterized problems FPT subset of or equal to W[1] subset of or equal to W[2] subset of or equal to ... subset of or equal to W[SAT] subset of or equal to W[P] and identify natural complete problems for W[t] for t greater than or equal to 2. (In other papers we have shown many problems complete for W[1].) DOMINATING SET is shown to be complete for W[2], and thus is not fixed-parameter tractable unless INDEPENDENT SET, CLIQUE, IRREDUNDANT SET, and many other natural problems in W[2] are also fixed-parameter tractable. We also give a compendium of currently known hardness results as an appendix.