[Solved]: Hardness proof of EVEN-ODD PARTITION

Problem Detail: 

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)

Asked By : Vor

Answered By : Karolis Juodelė

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

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/19271

 Ask a Question

 Download Related Notes/Documents