
Composing
Equipotent Teams 


Authors: 
Mark
Cieliebak, Stephan Eidenbenz, and Aris Pagourtzis 
Reference: 
In
"Proceedings of the 14th International Symposium on Fundamentals of Computation
Theory (FCT 2003)", Malmö, Sweden, August 2003. Springer, LNCS 2751,
pp. 98108, 2003 
Download: 
Postscript
(.ps) or PDF (.pdf) 
Abstract: 
We study the computational complexity of k Equal Sum Subsets, in
which we need to find k disjoint subsets of a given set of numbers
such that the elements in each subset add up to the same sum. This problem
is known to be NPcomplete. We obtain several variations by considering
different requirements as to how to compose teams of equal strength to play
a tournament. We present:
 A pseudopolynomial time algorithm for k Equal Sum Subsets
with k = O(1) and a proof of strong NPcompleteness for k
= \Omega(n).
 A polynomialtime algorithm under the additional requirement that
the subsets should be of equal cardinality c = O(1), and a
pseudopolynomial time algorithm for the variation where the common
cardinality is part of the input or not specified at all, which we proof
NPcomplete.
 A pseudopolynomial time algorithm for the variation where we look
for two equal sum subsets such that certain pairs of numbers are not
allowed to appear in the same subset.
Our results are a first step towards determining the dividing lines between
polynomial time solvability, pseudopolynomial time solvability, and strong
{\sf NP}completeness of subsetsum related problems; we leave an interesting
set of questions that need to be answered in order to obtain the complete
picture. 
Remarks: 
