<p>This is a reduction (attempt :-) from this slight variant of SUBSET SUM (which should be NPC) to prove that <strong>E2CSS</strong> is NP-complete:</p>

<p>Given integers $A = a_1,a_2,...,a_n\;; a_i &gt; 0$ (with the additional constraint that n is even) and a target sum $b$. Does exist $X \subseteq A$ such that $|X|=2m, m \geq 1$ (i.e. $|X|$ is even and greater than or equal to 2) and $sum(X)=b$?  </p>

<p>Reduction: suppose that $2^k &gt; b+\sum_{i=1}^n |a_i|$; then we expand $A$ adding a <em>dummy solution</em></p>

<p>$A' = A \cup \{ -2^k, 2^k + b\}$</p>

<p>If $X$ is a solution for the original problem, then  $X, Y= \{ -2^k, 2^k + b\}$ are two distinct solutions for $A'$ and target sum $b$. Now we can further expand $A'$ to $|A''|$ adding <em>padding pairs</em> of integers that do not affect the sums but can be used to "pad" $X$ and $Y$ up to $|X|+|Y|=|A''|$. We have
$|A'|=n+2$, so we add $n/2-1$ pairs $\{2^{k+i},-2^{k+i}\}$, $i=1..n/2-1$:</p>

<p>$A'' = \{a_1,...,a_n,-2^k, 2^k + b, 2^{k+1},-2^{k+1},...,2^{k+n/2-1},-2^{k+n/2-1}\}$, $|A''|=2n$</p>

<p>Using all the $n/2-1$ <em>padding pairs</em> we can build a set $Z$ such that $sum(Z)=0$ and $|Z|=2(n/2-1)=n-2$.</p>

<p>We can notice that using the dummy solution and the padding pairs we can build a set $Y'=Y \cup Z$, $sum(Y')=b$, $|Y'|=n$ (which is half the size of $A''$). So in order to get another <em>different</em> solution we  must use two or more of the $a_i$ plus some padding pairs.</p>

<p>In the figure a binary expansion of the elements of $A''$:
<img src="https://i.sstatic.net/mtWia.jpg" alt="enter image description here"></p>

<p>The above reduction works for any <em>fixed</em> $k$: just start with the (NP-complete) subset sum variant in which $k$ divides $n$ and $|X|\geq k$, then add $k-1$ dummy solutions (each dummy solution made with $k$ elements) and $(n/k-1)$ padding k-tuples.</p>

<p>If $k$ <em>is part of the input</em> (<strong>EkCSS</strong>), we have a simple generalization of the E2CSS problem and its NP-hardness follows immediately by the NP-completeness of E2CSS; the reduction is trivial: given an instance $A'',b$ of the E2CSS problem, just transform it to $A'',b,k=2$ which is a valid instance of the EkCSS problem. So EkCSS is NP-complete.</p>

<p>(Very informally) The <strong>EkCSS-diff</strong> should be NP-complete, too and the reduction from EkCSS is: "attach" to every $a_i$ a group of elements $T_i$ of size $m_i=(i+1)*n$:</p>

<p>$T_i= \{ a_i+1*2^u, 2*2^u,3*2^u,....,(m_i-1) 2^u,-2^u*\sum_{j=1}^{m_i-1} \}, |T_i|=(i+1)*n$</p>

<p>The first element of $T_i$ <em>which replaces</em> $a_i$, contains two detached "bit components" the original $a_i$ and $1*2^u$; but the only way to "clear" $1*2^u$ is to include the other elements of $T_i$ and the final one that is the only negative element (it "clears" all the previous $2^u$ components).</p>

<p>Every $T_i$ have distinct values for $u$ (and choosen in such a way that the sums don't interfere with each other and with the sum of the original $a_i$s).</p>

CC BY-SA 3.0
2013-11-30T17:46:33.077Z
Thankyou. Does the expansion trick work if we replace $2$ with $3,4,...$ or general $k$ or $\log^cn$?
Turbo
CC BY-SA 3.0
2013-12-01T09:26:36.470Z
I think that the same argument can be applied to any fixed $k\geq 2$  (it is easy to see that the corresponding starting subset sum variants are still NPC ). If you use $k$ as a parameter (or $\log^c n$) then you must "embed" the reduction from SUBSET SUM to the starting SUBSET SUM  in which it is required that $n$ is a multiple of $k$ and the size of the solution subset is still a multiple of $k$ (add shifted $a_i$ $k$-times and use as target $b$ the bitwise or of the shifted $b$). If you want I can expand this part and further formalize the proof. P.S. are you using it in another context?
Marzio De Biasi
CC BY-SA 3.0
2013-12-01T09:54:29.657Z
"are you using it in another context?" yes can the n' in your answer be not multiple of base n? I have not fully checked if n'=nk will be fine for me (but something tells it may be better).

Could you formalize the proof?
Turbo
CC BY-SA 3.0
2013-12-01T10:12:11.520Z
Ok, I'll expand it. But it came to my mind that $EkCSS$ (when $k$ is part of the input) is simply a *generalization* of E2CSS, and to prove that it is NP-complete you can use the immediate reduction from E2CSS (which is NPC) to EkCSS (just call EKCSS with the same input of the E2CSS problem and $k=2$). Is it correct?
Marzio De Biasi
CC BY-SA 3.0
2013-12-01T10:21:47.230Z
Ok, however, in your question, in the definition of EkCSS $k$ is not part of the input. You should distinguish between the two EkCSS version :-) (both are NPC).
Marzio De Biasi
CC BY-SA 3.0
2013-12-01T10:24:18.110Z
made the change..
Turbo
CC BY-SA 3.0
2013-12-01T14:14:06.297Z
@Kaveh: I think that the suggested edit (sum with the absolute values of $a_i$) is not needed because we start with a subset sum problem in which every $a_i > 0$
Marzio De Biasi
CC BY-SA 3.0
2013-12-01T17:27:09.027Z
Just Curious, if we insist that the k subsets are all of different size (call the problem EkCSS-diff), then is there a way to reduce EkCSS to EkCSS-diff? We could artificially extend a standard subset sum with $k-1$ additional different subsets of sizes $>n$ each and such that each subset sums to $b$, then the new sequence will have $k$ subsets of different size that sums to $b$ if there is a subset in the subset sum instance that sums to $b$. But this wont show, the size of subsets sum to $n$.
Turbo
CC BY-SA 3.0
2013-12-01T19:35:40.847Z
Ok makes sense and this is a great helpful answer:)!

Thankyou for the hard effort again!
Turbo
CC BY-SA 3.0
2013-12-03T15:29:14.800Z
@J.A: do you think that the result is interesting enough for a joint paper?
Marzio De Biasi
CC BY-SA 3.0
2013-12-03T15:50:49.483Z
Yes absolutely. I think the approach simplifies many other related proofs as well(your whole proof could be reduced to a sentence or two if argued precisely), that have been shown to be NPC and another thing that seems interesting is it works if we replace $a_i\in\Bbb Z$ with $a_i\in\Bbb F_p$ and it also seems extendable to counting problems. Give me some time. I am working on some applications and I am writing some other work. I will get back to you with details.
Turbo
CC BY-SA 3.0
2013-12-03T16:11:08.400Z
Perfect, if you want to contact me, my email is marziodebiasi [at] gmail [dot] com .
Marzio De Biasi
CC BY-SA 3.0
2014-01-29T16:58:23.063Z
What a nice outcome. =) Good luck!
Daniel Apon
CC BY-SA 3.0
2013-11-30T17:19:48.387Z
2013-12-01T19:29:42.500Z
2013-12-01T19:29:42.500Z
Marzio De Biasi
<p>$\underline{\mathsf{EQUAL\mbox{ }k-COMPLEMENTARY\mbox{ }SUBSET\mbox{ }SUM(EkCSS)} }$Problem:</p>

<p><em>Input</em>: $a_1,\dots,a_n,b\in \mathbb Z$, with distinct $a_i$ and $k\in\Bbb Z^+$.</p>

<p><em>Output</em>: $k$ $\mbox{ }\underline{not\mbox{ }necessarily\mbox{ }disjoint}$ subsets of $a_i$s of sizes $n_1,\dots,n_k$ satisfying $\sum_{i=1}^kn_i=n$ such that each subset sums to $b$. </p>

<p><strong>(1) Is $\mathsf{EkCSS}$ $NP$-complete?</strong></p>

<p><strong>(2) If we replace requiring $k$ subsets by requiring $\lceil\log^cn\rceil$ subsets for some fixed $c\in\Bbb R^+$ does the problem remain NP complete?</strong></p>

<p><strong>(3) Is $\mathsf{EkCSS-Diff}\mbox{ }$ $NP$-complete where $\mathsf{EkCSS-Diff}$ is same as $\mathsf{EkCSS}$ but with added condition $n_i\neq n_j\forall i\neq j$ (different subset sizes)?</strong></p>

<np-complete><subset-sum>
Multiple subset sum where subsets have complementary cardinality
Turbo
# Multiple subset sum where subsets have complementary cardinality

(Asked by: username_0 on 2013-11-30)

$\underline{\mathsf{EQUAL\mbox{ }k-COMPLEMENTARY\mbox{ }SUBSET\mbox{ }SUM(EkCSS)} }$Problem:

*Input*: $a\_1,\dots,a\_n,b\in \mathbb Z$, with distinct $a\_i$ and $k\in\Bbb Z^+$.

*Output*: $k$ $\mbox{ }\underline{not\mbox{ }necessarily\mbox{ }disjoint}$ subsets of $a\_i$s of sizes $n\_1,\dots,n\_k$ satisfying $\sum\_{i=1}^kn\_i=n$ such that each subset sums to $b$.

**(1) Is $\mathsf{EkCSS}$ $NP$-complete?**

**(2) If we replace requiring $k$ subsets by requiring $\lceil\log^cn\rceil$ subsets for some fixed $c\in\Bbb R^+$ does the problem remain NP complete?**

**(3) Is $\mathsf{EkCSS-Diff}\mbox{ }$ $NP$-complete where $\mathsf{EkCSS-Diff}$ is same as $\mathsf{EkCSS}$ but with added condition $n\_i\neq n\_j\forall i\neq j$ (different subset sizes)?**

**Tags:** np-complete, subset-sum

---

## 1 answers

### Answer by username_1 on 2013-11-30. Score: 2 | Accepted answer

This is a reduction (attempt :-) from this slight variant of SUBSET SUM (which should be NPC) to prove that **E2CSS** is NP-complete:

Given integers $A = a\_1,a\_2,...,a\_n\;; a\_i > 0$ (with the additional constraint that n is even) and a target sum $b$. Does exist $X \subseteq A$ such that $|X|=2m, m \geq 1$ (i.e. $|X|$ is even and greater than or equal to 2) and $sum(X)=b$?

Reduction: suppose that $2^k > b+\sum\_{i=1}^n |a\_i|$; then we expand $A$ adding a *dummy solution*

$A' = A \cup \{ -2^k, 2^k + b\}$

If $X$ is a solution for the original problem, then $X, Y= \{ -2^k, 2^k + b\}$ are two distinct solutions for $A'$ and target sum $b$. Now we can further expand $A'$ to $|A''|$ adding *padding pairs* of integers that do not affect the sums but can be used to "pad" $X$ and $Y$ up to $|X|+|Y|=|A''|$. We have
$|A'|=n+2$, so we add $n/2-1$ pairs $\{2^{k+i},-2^{k+i}\}$, $i=1..n/2-1$:

$A'' = \{a\_1,...,a\_n,-2^k, 2^k + b, 2^{k+1},-2^{k+1},...,2^{k+n/2-1},-2^{k+n/2-1}\}$, $|A''|=2n$

Using all the $n/2-1$ *padding pairs* we can build a set $Z$ such that $sum(Z)=0$ and $|Z|=2(n/2-1)=n-2$.

We can notice that using the dummy solution and the padding pairs we can build a set $Y'=Y \cup Z$, $sum(Y')=b$, $|Y'|=n$ (which is half the size of $A''$). So in order to get another *different* solution we must use two or more of the $a\_i$ plus some padding pairs.

In the figure a binary expansion of the elements of $A''$:
![enter image description here](https://i.sstatic.net/mtWia.jpg)

The above reduction works for any *fixed* $k$: just start with the (NP-complete) subset sum variant in which $k$ divides $n$ and $|X|\geq k$, then add $k-1$ dummy solutions (each dummy solution made with $k$ elements) and $(n/k-1)$ padding k-tuples.

If $k$ *is part of the input* (**EkCSS**), we have a simple generalization of the E2CSS problem and its NP-hardness follows immediately by the NP-completeness of E2CSS; the reduction is trivial: given an instance $A'',b$ of the E2CSS problem, just transform it to $A'',b,k=2$ which is a valid instance of the EkCSS problem. So EkCSS is NP-complete.

(Very informally) The **EkCSS-diff** should be NP-complete, too and the reduction from EkCSS is: "attach" to every $a\_i$ a group of elements $T\_i$ of size $m\_i=(i+1)\*n$:

$T\_i= \{ a\_i+1\*2^u, 2\*2^u,3\*2^u,....,(m\_i-1) 2^u,-2^u\*\sum\_{j=1}^{m\_i-1} \}, |T\_i|=(i+1)\*n$

The first element of $T\_i$ *which replaces* $a\_i$, contains two detached "bit components" the original $a\_i$ and $1\*2^u$; but the only way to "clear" $1\*2^u$ is to include the other elements of $T\_i$ and the final one that is the only negative element (it "clears" all the previous $2^u$ components).

Every $T\_i$ have distinct values for $u$ (and choosen in such a way that the sums don't interfere with each other and with the sum of the original $a\_i$s).

> **Comments:**
> **username_0**: Thankyou. Does the expansion trick work if we replace $2$ with $3,4,...$ or general $k$ or $\log^cn$?  
> **username_1**: I think that the same argument can be applied to any fixed $k\geq 2$  (it is easy to see that the corresponding starting subset sum variants are still NPC ). If you use $k$ as a parameter (or $\log^c n$) then you must "embed" the reduction from SUBSET SUM to the starting SUBSET SUM  in which it is required that $n$ is a multiple of $k$ and the size of the solution subset is still a multiple of $k$ (add shifted $a_i$ $k$-times and use as target $b$ the bitwise or of the shifted $b$). If you want I can expand this part and further formalize the proof. P.S. are you using it in another context?  
> **username_0**: "are you using it in another context?" yes can the n' in your answer be not multiple of base n? I have not fully checked if n'=nk will be fine for me (but something tells it may be better).  Could you formalize the proof?  
> **username_1**: Ok, I'll expand it. But it came to my mind that $EkCSS$ (when $k$ is part of the input) is simply a *generalization* of E2CSS, and to prove that it is NP-complete you can use the immediate reduction from E2CSS (which is NPC) to EkCSS (just call EKCSS with the same input of the E2CSS problem and $k=2$). Is it correct?  
> **username_1**: Ok, however, in your question, in the definition of EkCSS $k$ is not part of the input. You should distinguish between the two EkCSS version :-) (both are NPC).  
> **username_0**: made the change..  
> **username_1**: @Kaveh: I think that the suggested edit (sum with the absolute values of $a_i$) is not needed because we start with a subset sum problem in which every $a_i > 0$  
> **username_0**: Just Curious, if we insist that the k subsets are all of different size (call the problem EkCSS-diff), then is there a way to reduce EkCSS to EkCSS-diff? We could artificially extend a standard subset sum with $k-1$ additional different subsets of sizes $>n$ each and such that each subset sums to $b$, then the new sequence will have $k$ subsets of different size that sums to $b$ if there is a subset in the subset sum instance that sums to $b$. But this wont show, the size of subsets sum to $n$.  
> **username_0**: Ok makes sense and this is a great helpful answer:)!  Thankyou for the hard effort again!  
> **username_1**: @J.A: do you think that the result is interesting enough for a joint paper?  
> **username_0**: Yes absolutely. I think the approach simplifies many other related proofs as well(your whole proof could be reduced to a sentence or two if argued precisely), that have been shown to be NPC and another thing that seems interesting is it works if we replace $a_i\in\Bbb Z$ with $a_i\in\Bbb F_p$ and it also seems extendable to counting problems. Give me some time. I am working on some applications and I am writing some other work. I will get back to you with details.  
> **username_1**: Perfect, if you want to contact me, my email is marziodebiasi [at] gmail [dot] com .  
> **username_2**: What a nice outcome. =) Good luck!  

---

