1
$\begingroup$

I'm currently stuck showing $NP$-hardness of a problem of mine.

An instance of my problem (I call it (simple) pairwise $2$-Partitioning) is given by the following:

Given a set of tupels $B=\{(b_1,1),\ldots,(b_n,1)\}$, with $b_i\in\mathbb{N}_{>0}$.
Goal: A partition of $B$ into two subsets $S_1, S_2$ such that each element $b_i$ is exclusively either in $S_1$ or in $S_2$ and $$(\sum_{i\in S_1}b_i)+|S_2|=(\sum_{i\in S_2}b_i)+|S_1|$$

This can be seen in the following way. When $b_i$ is choosen from the pair $(b_i,1)$ to be in $S_1$ the other Element (in this case always $1$) must be in $S_2$.

I assume that this problem is $NP$-hard and that this can be shown by using the "classical" $2$-Partitioning-Problem where the goal is to partition a set $A=\{a_1,\ldots,a_n\}$ (with $a_i\in\mathbb{N}_{>0}$) into subsets $S_1,S_2$ s.t. the sum of these subset equals.

This far I wasn't able to show that the "classical" $2$-Partiting-Problem can be reduced to (simple) pairwise $2$-Partitioning.


My first attempt was to model some arbitrary but fixed instance of the $2$-Partitioning Problem with $A=\{a_1,\ldots,a_n\}$ to an instance of (simple) pairwise 2-Partitioning by constructing $B=\{(a_1-1,1),\ldots,(a_n-1,1)\}$ but somehow wasn't able to show that each $YES$-Instance of $A$ also is some $YES$-Instance of $B$.

$\endgroup$

1 Answer 1

1
$\begingroup$

I think you took the problem the wrong way, but your idea is good.

Let $A = \{a_1, …, a_n\}$ be an instance of $2$-$\texttt{Partition}$. Let $B = \{(a_1 + 1, 1), …, (a_n+1, 1)\}$. Then $A$ is a positive instance of $2$-$\texttt{Partition}$ if and only if $B$ is a positive instance of $\texttt{Pairwise}$ $2$-$\texttt{Partition}$:

  • suppose there exists $I_1\subset \{1, …, n\}$ such that $\sum\limits_{i\in I_1}a_i = \sum\limits_{i\notin I_1}a_i$. Then: \begin{align} \sum\limits_{i\in I_1}b_i + |\overline{I_1}| & =\sum\limits_{i\in I_1}(a_i +1)+ |\overline{I_1}|\\ & = \sum\limits_{i\in I_1}a_i + |I_1| + |\overline{I_1}|\\ & =\sum\limits_{i\notin I_1}a_i + |I_1| + |\overline{I_1}|\\ & = \sum\limits_{i\notin I_1}b_i + |I_1| \end{align}
  • the other way is done in the same manner.
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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