2
$\begingroup$

$\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)?

$\endgroup$

1 Answer 1

2
$\begingroup$

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

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

$\endgroup$
13
  • $\begingroup$ Thankyou. Does the expansion trick work if we replace $2$ with $3,4,...$ or general $k$ or $\log^cn$? $\endgroup$
    – Turbo
    Commented Nov 30, 2013 at 17:46
  • 1
    $\begingroup$ 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? $\endgroup$ Commented Dec 1, 2013 at 9:26
  • $\begingroup$ "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? $\endgroup$
    – Turbo
    Commented Dec 1, 2013 at 9:54
  • 1
    $\begingroup$ 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. $\endgroup$
    – Turbo
    Commented Dec 3, 2013 at 15:50
  • 1
    $\begingroup$ Perfect, if you want to contact me, my email is marziodebiasi [at] gmail [dot] com . $\endgroup$ Commented Dec 3, 2013 at 16:11

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.