0
$\begingroup$

After removing multi-sets and sets that have elements that don't exist in $S$.

$S$ = $[9,6,7,4,5,1,8]$

$C$ =$[[9,6,7],[4,5],[1,8]]$

Transform the values in $C$ of the shared index values with $S$. (This must be done before touching $S$)

$C$ = $[[1,2,3],[4,5],[6,7]]$

And do the same for $S$

$S$ = $[1,2,3,4,5,6,7]$

Square each $x$ integer in both $S$ and $C$

$f(x)$ = $x^2$, $x ∈ S$ then $C$

$S$ = $[1, 4, 9, 16, 25, 36, 49]$

$C$ = $[[1,4,9],[16,25],[36,49]]$

Then remove all sets with repeating sums to prevent false positives. This means no $[1],[1]s...$ that could be used, to sum up to the total sum of $S$, This also means $[1,4,9]$ or $[4,9,1]$. (leave one though!)

  1. After the transformation is complete use subset-sum solver and define total-sum as $140$ (total-sum of $s$)
  2. Define list of integers as a summed up set of $C$ = $[[14],[41],[85]]$
  3. Run Algorithm and get the solution

Question

Will this reduction of Exact Cover into Subset-Sum every yield a false positive?

$\endgroup$
1
$\begingroup$

If you're not really sure whether a reduction will work, it probably won't. Whenever you are making a reduction you should always have a plan of how to prove it correct.

In this case, we're looking to see whether $1^2+2^2+3^2+...+n^2$ can be written as a sum of squares in some other way (which would be a false positive).

We have that $4^2=2^2+2^2+2^2+2^2$. This is enough to construct a counterexample.

Let $S=\{1,2,3,4,5,6,7\}$ and $C=\{\{1,2\},\{2,3\},\{2,5\},\{2,6\}\,\{2,7\},\{1,3,4,5,6,7\}\}$.

There is no exact cover (the only way to get $4$ is to take $\{1,3,4,5,6,7\}$ but then we cannot take any other set since all of them overlap).

However, we have that:

$$1^2+2^2+3^2+4^2+5^2+6^2+7^2=(1^2+2^2)+(2^2+3^2)+(2^2+5^2)+(2^2+6^2)+(2^2+7^2)$$

Thus, we can conclude the reduction does not work.

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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