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: |