Can I read Linear FPT reductions and computational lower bounds on EtoBox?

Linear FPT reductions and computational lower bounds by Jianer Chen; Xiuzhen Huang; Iyad A. Kanj; Ge Xia is a scholarly article available to read on EtoBox.

What is Linear FPT reductions and computational lower bounds about?

We develop new techniques for deriving very strong computational lower bounds for a class of well-known NP-hard problems, including weighted satisfiability, dominating set, hitting set, set cover, clique, and independent set. For example, although a trivial enumeration can easily test in time O(n k ) if a given graph of n vertices has a clique of size k, we prove that unless an unlikely collapse occurs in parameterized complexity theory, the problem is not solvable in time f (k)n o(k) for any function f , even if we restrict the parameter value k to be bounded by an arbitrarily small function of n. Under the same assumption, we prove that even if we restrict the parameter values k to be Θ(μ(n)) for any reasonable function μ, no algorithm of running time n o(k) can test if a graph of n vertices has a clique of size k. Similar strong lower bounds are also derived for other problems in the above class. Our techniques can be extended to derive computational lower bounds on approximation algorithms for NP-hard optimization problems. For example, we prove that the NP-hard distinguishing substring selection problem, for which a polynomial time approximation scheme has been recently develo

Author

Jianer Chen; Xiuzhen Huang; Iyad A. Kanj; Ge Xia

Publisher

ACM

Published

2004

Language

EN