# Reduction to equipartition problem from the partition problem?

Equipartition Problem:

Instance: $2n$ positive integers $x_1,\dots,x_{2n}$ such that their sum is even. Let $B$ denote half their sum, so that $\sum x_{i} = 2B$.

Query: Is there a subset $I \subseteq [2n]$ of size $|I| = n$ such that $\sum_{i \in I} x_{i} = B$?

Can the partition problem - same as the above but without the restriction on $|I|$ - be reduced to the above problem ?

• Yes, Equipartition is NP-complete and there is p-time reduction to it from Partition problem. See SP12 in Garey and Johnson. – Mohammad Al-Turkistany Mar 23 '12 at 17:51

As noted in the comments, the EQUIPARTITION problem is also NP-complete. The basic idea of reducing PARTITION to it is to add elements so that they can be partitioned complementary to the original elements (thus yielding an equipartition) but in a way that ensures that new and old elements can not cancel each other out. The latter can be achieved by choosing the new elements sufficiently large.

Let $A = \{a_1, \dots, a_n\} \subseteq \mathbb{N}_+$ be an instance of PARTITION. Construct an instance $f(A)$ of EQUIPARTITION by

$\qquad \displaystyle f(A) = A \cup \{ a_{n+i} \mid a_{n+i} = 2B \cdot a_i, a_i \in A \}$

with $2B = \sum_{a \in A} a$. It is clear that $f$ can be computed in deterministic polynomial time. We have to show that $A$ is a YES-instance of PARTITION if and only if $f(A)$ is a YES-instance of EQUIPARTITION.

• Let $A$ be a YES-instance of PARTITION, that is there is $I \subset [n]$ with $\sum_{i \in I} a_i = B$. Then,

$\qquad \displaystyle I' = I \cup \{n+i \mid i \in \overline{I} = [n] \setminus I \}$

is a solution of $f(A)$; note that $|I'| = n$ and $\sum_{i \in I'} a_i = B + 2B^2 = \sum_{i \in \overline{I'}} a_i$. Thus, $f(A)$ is a YES-instance of EQUIPARTITION.

• Let $f(A)$ be a YES-instance of EQUIPARTITION. Let $I' = I \cup J$ a solution of $f(A)$ with $I \subseteq [n]$ and $J \subseteq [2n] \setminus [n]$ ($I$ contains the indices chosen from $A$, $J$ the new ones), and $\overline{I'} = \overline{I} \cup \overline{J}$ its complement, similarly partitioned. That is, $\sum_{i \in I'} a_i = \sum_{i \in \overline{I'}} a_i$

Assume towards a contradiction that $\sum_{i \in I} a_i \neq \sum_{i \in \overline{I}} a_i$; without loss of generality assume $\sum_{i \in I} a_i > \sum_{i \in \overline{I}} a_i$. Now we have that

$\qquad \displaystyle 0 < \sum_{i \in \overline{J}} a_i - \sum_{i \in J} a_i = \sum_{i \in I} a_i - \sum_{i \in \overline{I}} a_i < 2B$

which contradicts the construction of $f(A)$; elements with indices in $J \cup \overline{J}$ are all (positive) multiples of $2B$ so the assumed difference is impossible. Therefore, $I$ is a solution of $A$ which is thus a YES-instance of PARTITION.

This concludes the proof, that is PARTITION $\leq_p$ EQUIPARTITION by virtue of $f$.