Variation on the Subset Sum Problem

Question

Given a nonempty set of integers, and given that there exists a subset of this set whose elements sum to zero, is finding the smallest such subset NP-complete?

Disclaimer: The above question involves part of ongoing research for my dissertation.

To flesh this out, this question is derived from the so-called "subset sum problem," which asks whether a given set of integers has a subset that sums to zero. For my case, however, we are assuming the existence of at least one such subset, and then wish to investigate whether finding the minimal such subset is NP-hard.

I have a hunch (in other words, nothing resembling formal proof) that my problem above is an NP-hard problem, because we are not assuming that the subset whose elements sum to zero is explicitly given in the hypothesis, so that finding the minimal such subset leaves us with a similar search mechanism for finding the existence of such a subset in the standard Subset Sum problem (which is known to be NP-complete).

Exploring the case if such a subset is known may also be a point of interest, as well.

This is my first real exploration into research, and this is also the first time during the course of my research that my advisor himself is not aware of the answer, so I am feeling "stuck" for the first time in the course of researching a topic.

The purpose of this post is not necessarily to find an explicit answer, unless someone is aware of a paper that directly or equivalently addresses this question (we have not yet been able to find one).

The focus of my dissertation is more algebraic in nature, and the complexity discussion above relates to a curiosity worthy of including in this research, rather than ascertaining a direct solution. I would appreciate any input or advice, specific papers or even general directions to look, as I continue to develop my researching skills and run into these "ruts" for the first time.

Since this is my first post in Overflow, I apologize if this breaks any rules, ethics, or etiquette appropriate this board. I am excited to discover an interactive online place with seasoned professional mathematicians, and I look forward to developing my own researching skills from what I learn from here.

Answer 1

This is merely a simplification of Tony Huynh's answer, but still more than a comment imho. Note that throughout, I work with multi sets (or sequences of integers) rather than sets. Reduce SUBSET SUM to SMALLEST SUBSET SUM as follows: Given an instance $(a_1, \ldots, a_n)$ of SUBSET SUM, let $b := -(a_1 + \ldots + a_n)$ and plug the sequence $(a_1, \ldots, a_n, b)$ into your fictional SMALLEST SUBSET SUM algorithm.

(1) Clearly $a_1 + \ldots + a_n + b = 0$, so your instance has a zero-sum subset.

(2) If the original instance has a zero-sum subset, then this is still a zero-sum subset in the modified instance, hence the smallest such set will have cardinality at most $n$.

(3) If the modified instance has a zero-sum subset of cardinality at most $n$, there are two cases

(a) It does not contain $b$. Then that is a zero-sum subset of the original instance.

(b) It is $\{ b \} \cup \{ a_i : i \in I \}$ for some (possibly empty) $I \subsetneq [n]$. Then $\sum_{i \in I} a_i = \sum_{i=1}^n a_i$ and thus $\{ a_j : j \notin I \}$ is a non-empty zero-sum subset.

Hence the original instance has a zero-sum subset if and only if the modified instance has a zero-sum subset of size at most $n$.

Answer 2

I believe your problem is indeed NP-hard, via the following reduction from subset sum. Let $(a_i)_{i=1}^n$ be an instance of SUBSET SUM. We will make an instance of SMALLEST SUBSET SUM as follows. Let $a_k$ be such that $a_k \neq 0$ and $|a_k|$ is minimal among all $a_i$. Let $p$ be the smallest prime which is at least $n$. Now scale each entry by a factor of $p$ and then append $p$ copies of $-a_k$ to the instance. Note that this new instance has a subset which sums to zero by construction. Now, run SMALLEST SUBSET SUM on the new instance. Observe that the original instance has a zero-sum set if and only if the new instance has a zero-sum set of size at most $n$.