0
$\begingroup$

Decision Problem: Given a set $S$, is there at least a given $N$ $>$ $1$ amount of solutions, for an $Exact~Cover~by~3-sets$ for $C%$?

$s$ = $1,2,3,4,5,6$

$c$ = $[[1,2,3],[4,3,2],[4,5,6],[5,1,6],[5,6,3]]$

Solutions

$[1,2,3],[4,5,6]$

$[4,3,2],[5,1,6]$

$N$ = $2$

Yes, there are $N$ solutions.

Algorithm

  1. Remove sets that have repeating elements

    (eg. [1,1,2] is deleted from $C$)

  2. Remove sets that have elements that don't exist in $S$

    (eg. [9,5,6] is deleted because $9$ not in $S$)

  3. Make sure all elements in $S$ exist in $C$.

$for$ a $in$ $range(0, length(s)):$

$~~~~~~~~$$IF$ $s[a]$ $not$ in $c$:

$~~~~~~~~~~~~~$OUTPUT NO

Convert $C$ into a complete list

$WHILE$ $c[i]$ has [brackets]:

$~~~~~~~~~~$ DELETE [BRACKETS] FROM $C$

now $c$ = $[1, 2, 3, 4, 3, 2, 4, 5, 6, 5, 1, 6, 5, 6, 3]$

Finally, Decide

$n$ = $('Enter~for~N:~'))$

$yes$ = $0$

$for$ a $in$ $range$(0, $length(c)):$

$~~~~~~$$if$ $c$.count($c$[a]) >= $n$ :

$~~~~~~~~~~$$yes$ = $1$

$~~~~~~$else:

$~~~~~~~~~~$OUTPUT NO

$~~~~~~~~~~$HALT

$if$ $yes$ == $1$ :

$~~~~$OUTPUT YES

Edit: The above should do the same below.

yes = 0
for a in range(0, length(s)):
    if c.count(s[a]) >= n:
        yes = 1
    else:
        OUTPUT('No')
        break

if yes == 1:
    OUTPUT('yes')

Facts to consider

  1. There cannot be any sets with elements that don't exist in $S$.

  2. There cannot be any sets with repeating elements.

  3. All elements in $S$ must exist in $C$. Else, a $no$ is given.
  4. $N$ must be > $1$
  5. If any element in $C$ occurs < $N$ times then the output must be $No$, because there wouldn't be at least $N$ solutions.

Question

Will this algorithm always work if the input is > $1$, and if no how would it fail?

$\endgroup$
  • $\begingroup$ If it fails, I will resort to using the counting method for $S$ and compare it to the number of times $S[a]$ occurs in $C$. $\endgroup$ – Dingle Berry May 30 at 22:39
  • 1
    $\begingroup$ $S = \{1, ..., 9\}$. $C = [[1, 2, 3], [4, 5, 6], [7, 8, 9], [4, 8, 9], [5, 6, 7]]$ $N=2$ $\endgroup$ – Vladislav Bezhentsev May 30 at 23:03
  • 1
    $\begingroup$ [[1, 2, 3], [4, 5, 6], [7, 8, 9]] and [[1, 2, 3], [4, 8, 9], [5, 6, 7]] Why these solutions are bad? $\endgroup$ – Vladislav Bezhentsev May 30 at 23:10
  • 1
    $\begingroup$ I ran it on input that we have discussed above. Do you agree that this input has at least two solutions? $\endgroup$ – Vladislav Bezhentsev May 30 at 23:26
  • 1
    $\begingroup$ What are you trying to do? It's HIGHLY unlikely that you will be able to find a poly-time algorithm for an NP-complete problem. $\endgroup$ – Vladislav Bezhentsev May 31 at 21:52

Your Answer

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

Browse other questions tagged or ask your own question.