Efficient reductions and algorithms for variants of Subset Sum
share
Given (a_1, β¦, a_n, t) ββ€_β₯ 0^n + 1, the Subset Sum problem (π²π²π΄π¬) is to decide whether there exists S β [n] such that β_i β S a_i = t. There is a close variant of the π²π²π΄π¬, called π²ππ»ππΎπΒ π―πππ½ππΌπ. Given positive integers a_1, ..., a_n and a target integer t, the π²ππ»ππΎπΒ π―πππ½ππΌπ problem asks to determine whether there exists a subset S β [n] such that β_i β S a_i=t. There is a pseudopolynomial time dynamic programming algorithm, due to Bellman (1957) which solves the π²π²π΄π¬ and π²ππ»ππΎπΒ π―πππ½ππΌπ in O(nt) time and O(t) space. In the first part, we present search algorithms for variants of the Subset Sum problem. Our algorithms are parameterized by k, which is a given upper bound on the number of realisable sets (i.e.,Β number of solutions, summing exactly t). We show that π²π²π΄π¬ with a unique solution is already NP-hard, under randomized reduction. This makes the regime of parametrized algorithms, in terms of k, very interesting. Subsequently, we present an Γ(kΒ· (n+t)) time deterministic algorithm, which finds the hamming weight of all the realisable sets for a subset sum instance. We also give a poly(knt)-time and O(log(knt))-space deterministic algorithm that finds all the realisable sets for a subset sum instance. In the latter part, we present a simple and elegant randomized Γ(n + t) time algorithm for π²ππ»ππΎπΒ π―πππ½ππΌπ. Moreover, we also present a poly(nt) time and O(log^2 (nt)) space deterministic algorithm for the same. We study these problems in the unbounded setting as well. Our algorithms use multivariate FFT, power series and number-theoretic techniques, introduced by Jin and Wu (SOSA'19) and Kane (2010).
READ FULL TEXT