Subset sum with multiple lists

Question

Given n lists of m elements each we need to obtain sum S by selecting one element from each list. Is corresponding decision problem NP-complete? Are there papers about it?

Answer 1

I don't know if this problem has a name (yet), but it is at least weakly NP-hard since we can reduce subset sum to it:

Given a subset sum instance with item set $A = \{a_1,\ldots,a_n\}$ and target value $B$, we set $S = B$, $m = 2$, and create one list for each $a \in A$ with the two values $(a, 0)$. Basically, for each $a \in A$, you then have the choice to either take it (if you take $a$) or to not select it (if you take $0$). The requirement to "select one element from each list" is then translated into "you are allowed to pick each element at most once".

Answer 2

Your problem is called Muliple-Choice Subset Sum (MCSS). The book Knapsack Problems by Hans Kellerer, Ulrich Pferschy and David Pisinger mentions this problem as a special case of the Multiple-Choice Knapsack (MCKP) (Chapter 11.10.1). [Hereby, Multiple-Choice Knapsack is defined very similarly to your problem: Given an instance of Knapsack in which the items are divided into list. One can pick one item per list.]

MCSS is NP-hard by the reduction in the previous post.

MCSS can be solved in pseudopolynomial time: The above mention book provides some pseudopolynomial algorithms for the more general MCKP.

Recently, we have submitted a paper at the CTW23, in which we proved that MCSS is W[1]-hard with respect to number of lists. The paper is not yet publicly accessible, but I'll link it here, as fast as I can.

---

I want to briefly talk a bit about weak NP-hardness in response to the previous post.

Why is the above mentioned not correct? You can not show that a problem is weakly NP-hard by a reduction from some weakly NP-hard problem. Remember the definition of NP-hardness: For any NP-hard problem $\Pi_h$ and a problem $\Pi_2\in \text{NP}$, there is a karp-reduction from $\Pi_2$ to $\Pi_h$. Thus, there is a reduction from Subset Sum to Clique which is not weakly NP-hard.

What are weakly-NP-hard problems? These are problems that can be solved in $g(k+|I|)$ time, where $g$ is a polynomial, $k$ is an integer that is given in the instance and $|I|$ is the size of the instance.

Why is that possible? I'll describe this at the example of Subset Sum. An instance of Subset Sum for a computer looks something like: 01010#11010#00101#.....#10100001110101011110110010 Here, your target sum is 10100001110101011110110010 in binary, or in 42424242 in decimal. Observe that the length of the string is a lot (logarithmic factor) smaller. Thus, the size of the input might be a lot smaller than 42424242 and the algorithm running in $g(k+|I|)$ time does not provide evidence that Subset Sum is in P.

What are then strongly-NP-hard problems? A problem is called strongly NP-hard, if the problem remains NP-hard, even if every integer in the instance can be bounded polynomially in the size of the instance. One example is Clique. An instance $(G,k)$ surely contains an integer $k$, but we may assume that $k\le |V|$, as we can return no otherwise.