Tight lower bounds for certain parameterized NP-hard problems
Tight lower bounds for certain parameterized NP-hard problems
复制标题
DOI：
10.1016/j.ic.2005.05.001
复制
发表时间：
2005-09-15
影响因子：
1
通讯作者：
Xia, G
中科院分区：
文献类型：
--
作者：
Chen, J;Chor, B;Xia, G
在参数化复杂性理论框架下，我们得到了一些著名的NP-困难问题的计算复杂性的严格下界。我们首先证明它的一般结果，即深度t回路上的参数化加权可满足性问题不能在时间n（O（k））m（O（1））内求解。其中n是电路输入长度，in是电路大小，k是参数，除非W-层次的第（t - 1）级W[t - 1]塌陷到FPT。证明了一类参数化的NP-难问题，包括加权SAT，碰集。设置掩护。和功能集。不能在时间n（O（k））m（O（1））内求解，其中n是要从中选择k个元素的全集的大小，in是实例大小，除非W-层次的第一层W[1]坍缩为FPT。我们还证明了另一类包含加权q-SAT的参数化问题（对于任何固定的q >= 2），CLIQUE，INDEPENDENT SET和DOMINATING SET，不能在时间n（O（k））内解决，除非Papadimitriou和Yarmakakis引入的句法类SNP中的所有搜索问题都可以在次指数时间内解决。注意所有这些参数化问题都有运行时间为n（k）m（O（1））或O（n（k））的平凡算法。(c)2005年爱思唯尔公司All rights reserved.
Based on the framework of parameterized complexity theory,. we derive tight lower bounds on the computational complexity for a number of well-known NP-hard problems. We start by proving it general result, namely that the parameterized weighted satisfiability problem on depth-t circuits cannot be solved in time n(O(k))m(O(1)). where n is the circuit input length, in is the circuit size, and k is the parameter, unless the (t - 1)-st level W[t - 1] of the W-hierarchy collapses to FPT By refining this technique. we prove that a group of parameterized NP-hard problems, including weighted sat, hitting set. set cover. and feature set. cannot be solved in time n(O(k))m(O(1)), where n is the size of the universal set from which the k elements are to be selected and in is the instance size, unless the first level W[1] of the W-hierarchy collapses to FPT We also prove that another group of parameterized problems which includes WEIGHTED q-SAT (for any fixed q >= 2), CLIQUE, INDEPENDENT SET, and DOMINATING SET, cannot be solved in time n(O(k)) unless all search problems in the syntactic class SNP, introduced by Papadimitriou and Yarmakakis, are solvable in subexponential time. Note that all these parameterized problems have trivial algorithms of running time either n(k)m(O(1)) or O(n(k)). (c) 2005 Elsevier Inc. All rights reserved.