Equal Sum Subsets: Complexity of Variations
   
Authors: Mark Cieliebak, Stephan Eidenbenz, Aris Pagourtzis, and Konrad Schlude
Reference: Technical Report 370, ETH Zurich, Department of Computer Science, July 2002
Download: Postscript (.ps) or PDF (.pdf)
Abstract:
We start an investigation into the complexity of variations of the Equal Sum Subsets problem, a basic problem in which we are given a set of numbers and are asked to find two disjoint subsets of the numbers that add up to the same sum. While Equal Sum Subsets is known to be NP-complete, only very few studies have investigated the complexity of its variations. In this paper, we show NP-completeness for two very natural variations, namely Factor-r Sum Subsets, where we need to find two subsets such that the ratio of their sums is exactly r, and k Equal Sum Subsets, where we need to find k subsets of equal sum. In an effort to gain an intuitive understanding of what makes a variation of Equal Sum Subsets NP-hard, we study several variations of Equal Sum Subsets in which we introduce additional requirements that a solution must fulfill (e.g., the cardinalities of the two sets must differ by exactly one), and prove NP-hardness for these variations. Finally, we investigate and show NP-hardness for the Equal Sum Subsets from Two Sets problem and its variations, where we are given two sets and we need to find two subsets of equal sum. Our results leave us with a family of NP-complete problems that gives insight on the sphere of NP-completeness around Equal Sum Subsets.
Remarks:


Note: electronic versions may not always correspond exactly to printed versions.