Subset Sum With Interval Target

Question

Define the subset sum with interval target problem (SSITP) as follows:

SSITP Input:
A multiset $S = \{a_1, …, a_p\}$ of positive integers $a_i$ such that $\sum_{a_i \in S} a_i = T$.

SSITP Output:

• True, if there is a subset $S’ \subseteq S$ such that $\sum_{x \in S'} x \in \lceil \frac{1}{2}T \rceil .. \lfloor \frac{3}{4}T \rfloor$.
• False, otherwise.

Where $a .. b$, for two integers $a$ and $b$, is an integer interval including every integer between $a$ and $b$: $a, a+1, a+2, \dots, b-2, b-1, b$.

Is SSITP NP-hard?
Does introducing negative integers in the multiset $S$ change the hardness of the SSITP?

Answer 1

With positive integers only

Consider the largest element $a_m$ in the input. We have the following cases:

1. $a_m \in [\lceil\frac{1}{2}T\rceil, \lfloor\frac{3}{4}T\rfloor]$. We can simply choose $\{a_m\}$ and we are done: the answer is YES.
2. $a_m \in (\lfloor\frac{3}{4}T\rfloor, T]$. Any subset that includes $a_m$ is too large, and taking all the remaining elements together is strictly less than $T-\lfloor\frac{3}{4}T\rfloor = \lceil\frac{1}{4}T\rceil$, which is too small: the answer is NO.
3. $a_m \in [\lceil\frac{1}{4}T\rceil, \lceil\frac{1}{2}T\rceil)$. We can always take all elements except $a_m$ and get a subset in the correct range: the answer is YES.
4. $a_m \in [0, \lceil\frac{1}{4}T\rceil)$. We can choose elements in any order, stopping as soon as we get a total in the desired range. To see that this must occur, note that the elements sum to strictly more than $\lfloor\frac{3}{4}T\rfloor$, and for it not to occur would require that choosing some element $a_i$ takes the sum of elements chosen so far from strictly below $\lceil\frac{1}{2}T\rceil$ to strictly above $\lfloor\frac{3}{4}T\rfloor$ -- but such an element would have to be at least $\lfloor\frac{3}{4}T\rfloor - \lceil\frac{1}{2}T\rceil + 2 = \lfloor\frac{3}{4}T\rfloor + \lfloor-\frac{1}{2}T\rfloor + 2 \ge \lfloor\frac{1}{4}T\rfloor + 1 \ge \lceil\frac{1}{4}T\rceil > a_m$, which contradicts the maximality of $a_m$. So the desired range must be hit, and the answer is YES.

The solution can always be found in linear time by checking all cases, so the problem cannot be NP-complete unless P=NP.

Answer 2

With negative integers permitted

Unlike the SSITP problem restricted to positive integers, when negative integers are permitted the problem is NP-complete. I'll show this by reduction from ordinary Subset Sum (SS). The idea of the reduction is to append extra numbers that force the target range to collapse to the single value 3, and to mess with the numbers in the original input so that the odd target value can only be achieved in very constrained ways that correspond straightforwardly to solutions to the original instance. I needed to add the "crumb" elements to make sure that when we have an SSITP solution, at least one element from the original SS instance must be chosen.

Reduction

Given an instance $X = b_1, \dots, b_n$ of SS, where each $b_i$ can be positive, negative or zero and the target value is zero, we construct an instance $Y = a_1, \dots, a_p$ of SSITP as follows:

• Set $a_i = 8nb_i + 4$ for all $i \in [n]$. Call these elements the meat, $M$.
• Append $a_{n+1} = 2-8nU$, where $U = \sum_i{b_i}$. (I think of this element as "ballast" -- it exists only to weigh the sum down towards zero.)
• Append $a_{n+2} = 3-4n$. (I think of this element as the "cornerstone" -- we can show that any solution must contain it.)
• Finally append $n-1$ copies of 4, and $n-1$ copies of -4, as $a_{n+3}, \dots, a_{3n}$. Call these elements the crumbs, $C$. (So in all there are $p=3n$ elements.)

Appending the extra numbers forces the total $T=\sum_i^p{a_i}$ to be 5. This shrinks the "interval" of allowed values to the single value $\lceil\frac{1}{2}5\rceil = \lfloor\frac{3}{4}5\rfloor = 3$.

$X$ is a YES-instance of SS $\implies$ $Y$ is a YES-instance of SSITP: For each $b_i$ in the solution to $X$, choose $a_i$ for the solution to $Y$. Suppose there are $k \ge 1$ such elements: The sum so far is $8n(0)+4k=4k$. Now choose $n-k$ copies of 4, bringing the sum so far to $4n$. Finally choose $a_{n+2} = 3-4n$, bringing the total to 3.

$Y$ is a YES-instance of SSITP $\implies$ $X$ is a YES-instance of SS: The target is 3, which is odd, so the solution to $Y$ must contain an odd number. The only odd number available is $a_{n+2} = 3-4n$, so it must appear in the solution. If $a_{n+1} = 2-8nU$ also appears in the solution, then the remaining elements must sum to $3-(3-4n)-(2-8nU) = 4n+8nU-2$ -- but that number is not divisible by 4, and all other elements are multiples of 4, so this is not possible. Therefore the solution to $Y$ contains only $a_{n+2} = 3-4n$, in addition to a subset of $M\cup C$ that sums to $4n$. Observe that this subset must contain at least one meat element, since the greatest sum achievable using only crumbs is $4(n-1)$.

We want the $8nb_i$-terms within the chosen subset of $k \ge 1$ meat elements to sum to zero, so that we can simply choose the corresponding elements $a_i$ to get a solution to $X$. Suppose towards contradiction that they do not: Then either the chosen subset of $M$ sums to at least $8n + 4k \ge 8n$, or it sums to at most $-8n+4k \le -4n$. In the first case, to reach a total of $4n$ from $8n$ we must use crumbs to subtract $4n$, but the most we can subtract this way is $4(n-1)$, so this case cannot happen. Similarly, in the second case, to reach a total of $4n$ from $-4n$ we must use crumbs to add $8n$, but the most we can add this way is $4(n-1)$, so this case cannot happen either. Therefore the only way that the chosen subset of $M\cup C$ can sum to $4n$ is if the $8nb_i$-terms of the chosen subset of $M$ sum to zero, as desired. Then we can simply choose corresponding elements $a_i$ to get a solution to $X$.

We have established that a YES solution to the constructed instance of SSITP $\iff$ the original SS instance has a YES solution, so a NO solution to the constructed instance of SSITP $\iff$ the original SS instance has a NO solution. The construction is clearly polynomial-time, so SSITP with negative integers permitted is NP-complete.