In the Equal-Subset-Sum problem, we are given a set @math of @math integers and the problem is to decide if there exist two disjoint nonempty subsets @math , whose elements sum up to the same value. The problem is NP-complete. The state-of-the-art algorithm runs in @math time and is based on the meet-in-the-middle technique. In this paper, we improve upon this algorithm and give @math worst case Monte Carlo algorithm. This answers the open problem from Woeginger's inspirational survey. Additionally, we analyse the polynomial space algorithm for Equal-Subset-Sum. A naive polynomial space algorithm for Equal-Subset-Sum runs in @math time. With read-only access to the exponentially many random bits, we show a randomized algorithm running in @math time and polynomial space.
has some connections to the study of the structure of DNA molecules @cite_15 @cite_19 @cite_26 . considered @math - , in which we need to find @math disjoint subsets of a given set with the same sum. They obtained several algorithms that depend on certain restrictions of the sets (e.g., small cardinality of a solution). In the following work, considered other variants of and proved their NP-hardness.
@cite_19 @cite_15 @cite_26
1598605111 1865467296 2102000201
The EQUAL SUM SUBSETS problem, where we are given a set of positive integers and we ask for two nonempty disjoint subsets such that their elements add up to the same total, is known to be NP-hard. In this paper we give (pseudo-)polynomial algorithms and or (strong) NP-hardness proofs for several natural variations of EQUAL SUM SUBSETS. Among others we present (i) a framework for obtaining NP-hardness proofs and pseudopolynomial time algorithms for EQUAL SUM SUBSETS variations, which we apply to variants of the problem with additional selection restrictions, (ii) a proof of NP-hardness and a pseudo-polynomial time algorithm for the case where we ask for two subsets such that the ratio of their sums is some fixed rational r > 0, (iii) a pseudo-polynomial time algorithm for finding k subsets of equal sum, with k = O(1), and a proof of strong NP-hardness for the same problem with k = Ω(n), (iv) algorithms and hardness results for finding k equal sum subsets under the additional requirement that the subsets should be of equal cardinality. Our results are a step towards determining the dividing lines between polynomial time solvability, pseudo-polynomial time solvability, and strong NP-completeness of subset-sum related problems. The problem to find the coordinates of n points on a line such that the pairwise distances of the points form a given multi-set of (n 2 ) distances is known as Partial Digest problem, which occurs for instance in DNA physical mapping and de novo sequencing of proteins. Although Partial Digest was – as a combinatorial problem – already proposed in the 1930’s, its computational complexity is still unknown.