On the parameterized complexity of k-SUM
Amir Abboud, Kevin Lewi, Ryan Williams · arXiv (Cornell University) · 2013
In the k-SUM problem, we are given a set of numbers and asked if there are k of them which sum to 0. The case of k = 3 has been extensively studied in computational geometry, and known to be intimately related to many low-dimensional problems. The case of arbitrary k is the natural parameterization of Subset Sum and is well-known in parameterized algorithms and complexity. We present new FPT reductions between the k-SUM problem and the k-Clique problem, yielding several complexity-theoretic and algorithmic consequences. Our reductions show that k-SUM on “small” numbers (in the range [−n f(k) ,n f(k) ] for any computable function f) is W[1]complete, and that k-SUM (in general) is W[1]-complete under a common derandomization assumption. These results effectively resolve the parameterized complexity of k-SUM, initially posed in 1992 by Downey and Fellows in their seminal paper on parameterized intractability [11, 12]. Our method is quite general and applies to other weighted problems as well.