# How to partition a set in order to minimize the number of the elements and their interactions?

Given two sets $$S_1$$ and $$S_2$$ of $$n$$ elements each. Each set $$S_1$$ (resp. $$S_2$$) has a revenue $$R_1$$ (resp. $$R_2$$). Each element $$i$$ of $$S_1$$ (resp. $$S_2$$) has a gain $$g_{i1}$$ (resp. $$g_{i2}$$). From set $$S_1$$ (resp. $$S_2$$), choose a subset of elements $$O_1$$ (and $$O_2$$) such that:

• $$\sum_{i\in O_1}g_{i1}\geqslant R_1$$;
• $$\sum_{i\in O_2}g_{i2}\geqslant R_2$$;
• $$|O_1|+|O_2|+|O_1\cap O_2|$$ is minimized.

Can we solve this problem in polynomial-time?

I started by a greedy approach which chooses the elements by increasing order of their gains. I tried few examples but this does not provide optimal results.

I am now trying to prove that it is NP-hard using a reduction from PARTITION. Any hints?

Consider the following two variants of subset sum problem:

# Variant 1

Given a set of $$2n$$ positive integer elements and a positive integer target $$W$$, is there a subset with size $$n$$, whose sum is $$W$$?

# Variant 2

Given a set of $$n$$ positive integer elements and a positive integer target $$W$$, where $$(\text{the maximum element})< 2\times(\text{the minimum element})$$, is there a subset whose sum is $$W$$?

Variant 1 is NP-hard by a reduction from one-in-three 3-SAT (almost the same reduction from 3SAT to the normal subset sum problem, except that we do not need the $$s$$ and $$t$$ values, and the target is always $$111\ldots1$$).

Variant 2 is also NP-hard by a reduction from Variant 1. Given an instance of Variant 1, we add a large enough integer $$M$$ to each element so that the new elements satisfy the constraint in Variant 2. Now the answer to Variant 1 is "yes" if and only if there is a subset of the new elements whose sum is $$W+nM$$ (since $$M$$ is large enough, the subset must have size $$n$$).

Now we show a reduction from Variant 2 to (the decision version of) your problem, so your problem is NP-hard.

Given an instance of Variant 2, we construct $$S_1=S_2$$ as the same set as the given instance. Let $$s$$ denote the sum of all elements. We set $$R_1=W$$ and $$R_2=s-W$$. The gain of each element is the same as itself.

Now if there is a subset $$O\subseteq S_1=S_2$$ whose sum is $$W$$, then we can choose $$O_1=O$$ and $$O_2=S_2\backslash O$$, meaning there is a solution to your problem with $$|O_1|+|O_2|+|O_1\cap O_2|\le n$$.

On the other hand, if there is a solution to your problem with $$|O_1|+|O_2|+|O_1\cap O_2|\le n$$, then $$2|O_1\cap O_2|\le n-|O_1\cup O_2|$$. Let $$\min$$ and $$\max$$ be the minimum and maximum elements respectively. We have $$\sum_{e\in O_1\cap O_2}e\le |O_1\cap O_2|\max\le 2|O_1\cap O_2|\min\le(n-|O_1\cup O_2|)\min\le\sum_{e\notin O_1\cup O_2}e.$$

This means $$\sum_{e\notin O_1}e=\sum_{e\in O_2}e-\sum_{e\in O_1\cap O_2}e+\sum_{e\notin O_1\cup O_2}e\ge \sum_{e\in O_2}e\ge s-W.$$

Note $$\sum_{e\in O_1}e\ge W$$ and $$\sum_{e\notin O_1}e+\sum_{e\in O_1}e=s$$, we have $$\sum_{e\in O_1}e=W$$ and $$\sum_{e\notin O_1}e =s-W$$, which means there is a subset $$O\subseteq S_1=S_2$$ whose sum is $$W$$.

• Thanks. Is the variant 2 known in the literature? Do you mean that the gains are constructed so that the max gain is at most twice the min gain?
– zdm
Mar 15, 2019 at 15:30
• @zdm The max gain is at most twice the min gain because so is the input of Variant 2, not because of the construction. I don't think Variant 2 is studied in the literature because it is trivial. Mar 15, 2019 at 15:35
• In the reduction from Variant 1 to Variant 2, say I have an instance of Variant 1 as follows: $\{1,2,3,4,5,6\}$ and $W=11$. How can I choose $M$ ?
– zdm
Mar 15, 2019 at 16:25
• @zdm It is enough to let $M$ be the sum of all elements. In your example we can choose $M=21$. Mar 15, 2019 at 16:32
• I tried some examples with your reduction. Given an instance of Variant 2, when I create an instance of my problem I always find a solution with $O_1\cap O_2=\emptyset$. Does this mean that the problem is still NP-hard even if I want to minimize $|O_1|+|O_2|$?
– zdm
Mar 15, 2019 at 22:28