# Hardness proof of EVEN-ODD PARTITION

The PARTITION problem is NP-complete:

INSTANCE: finite set $A$ and a size $s(a) \in \mathbb{Z}^+$ for each $a \in A$
QUESTION: Is there a subset $A' \subseteq A$ such that $\sum_{a \in A'} s(a) = \sum_{a \in A \setminus A'} s(a)$

The problem remains NP-complete even if the elements are ordered as $a_1,a_2,...,a_{2n}$ and we require that $A'$ contains exactly one of $a_{2i-1},a_{2i}$ for $1 \leq i \leq n$ (Garey and Johnson, Computers and Intractability).

This variant should be known as EVEN-ODD PARTITION.

Do you see a quick reduction to prove its hardness? (or do you know the paper where it was first defined and proved)

• A problem with that name was proven NP-complete in Garey, Michael R., Robert E. Tarjan, and Gordon T. Wilfong. "One-processor scheduling with symmetric earliness and tardiness penalties." Mathematics of Operations Research 13.2 (1988): 330-348. Sorry I can't access the paper right now, but I wonder if this is what you are looking for. – Juho Dec 25 '13 at 10:55
• @Juho: to be honest I didn't checked it because it was published in 1988 and the G&J Computers and Intractability (in which the problem is said to be NP complete) was published in 1979 and I was more interested in the reduction (and I found two papers in which they call it EVEN-ODD PARTITION with a reference to G&J for its NP-completeness). However the reduction is very simple (I found it by myself). – Vor Dec 25 '13 at 22:29

Let $b_i = a_{2i} - a_{2i-1}$. The problem is then finding $\sum \varepsilon_i b_i = 0$. Here $\varepsilon_i = 1$ if $a_{2i} \in A'$ and $-1$ otherwise. Let $B' = \{b_i \mid \varepsilon_i = 1\}$. Note that $\sum_{b \in B'} b = \sum _{b \in B \setminus B'} b$. Thus solving PARTITION of $B$ would solve EVEN-ODD PARTITION of $A$.
Let $b_{2i} = a_i$ and $b_{2i-1} = 0$. Note that if $b_{2i} \in B' \leftrightarrow a_i \in A'$ and $\sum_{B'} = \sum_{B \setminus B'}$ then $\sum_{A'} = \sum_{A \setminus A'}$. Thus solving EVEN-ODD PARTITION on $B$ would solve PARTITION on $A$.
Let $2^k > \sum_{a \in A} s(a)$. Then for each element $a_i \in A$ add to $B$ two elements:
$b_{2i-1} = 2^{2k+2i} + a_i$and
$b_{2i} = 2^{2k+2i} + a_i 2^k$.
The two consecutive elements cannot be contained in the same subset (due to the $2^{2k+2i}$ common "bit"), and $B$ can be even-odd partitioned into two equal sum subsets that have the same cardinality if and only if $A$ can be partitioned into two equal sum subsets.