Polynomial kernels for weighted problems

Kernelization is a formalization of efficient preprocessing for NP-hard problems using the framework of parameterized complexity. It has been asked many times whether there are deterministic polynomial kernelizations for SUBSET SUM and KNAPSACK. We answer both questions affirmatively by using an algorithm for compressing numbers due to Frank and Tardos (Combinatorica 1987). We further illustrate its applicability by giving polynomial kernels for weighted versions of several well-studied parameterized problems. Furthermore, when parameterized by the different item sizes we obtain a polynomial kernelization for SUBSET SUM and an exponential kernelization for KNAPSACK. Finally, we obtain kernelization results for polynomial integer programs. (C) 2016 Elsevier Inc. All rights reserved.