5
$\begingroup$

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 ?

$\endgroup$

migrated from cstheory.stackexchange.com Jun 12 '12 at 18:35

This question came from our site for theoretical computer scientists and researchers in related fields.

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

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$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.