5
$\begingroup$

I am trying to reduce Exact Cover to Fixed Exact Cover to show that Fixed Exact Cover is NP-Hard.

Exact Cover

Input

S = {x1, x2, ..., xn} (set)

P = {P1, P2, ..., Pm} (subsets of S)

Decision problem: Is there a subset {Pi1,Pi2,...,Piq} of P such that every element of S belongs to exactly one of the Pij:s?

Fixed Exact Cover

Input S, P from Exact Cover, and an integer K

Decision problem: Is there a subset {Pi1,Pi2,...,Pik} of P of size K such that every element of S belongs to exactly one of the Pij:s?

Given hint: K = n + 1

My initial reaction is to iterate through each element in S, and for each element create a subset for P. However, that will result result in K being one too small. I have tried many things, but I just can't seem to figure it out.

EDIT

Sorry I should have added this in the original question: (All the Pij :s are assumed to be distinct.) Furthermore, (we can define an instance (S′,P′,K=n+1) of FSEC. S′ will be S ∪ A and P′ will be F ∪ G where A and G are ”dummy” sets disjoint from S and P and such that the elements of G are subsets of A. If A and G are chosen in a clever way (S,P) will have an exact cover if and only if (S′,P′) has a n+1 size cover)

Example

S = {1,2,3,4}

P = {{1}, {2,3}, {2,4}, {4}}

Solution

{{1}, {2,3},{4}} (size 3)

K = 5

S' = {1,2,3,4,5,6,7,8}

P' = {{1}, {2,3}, {2,4}, {4}, {5}, {6},{7},{8}, {5,6},{5,6,7}, {5,6,7,8}}

Solution = {{1}, {2,3}, {4}, {5,6,7}, {8}} (size 5)

$\endgroup$
5
$\begingroup$

Add $n$ empty sets, and choose $K = n + 1$. Every solution for the original problem is (without loss of generality) of size between $1$ to $n$, so using the empty sets you can complete it to a solution of size exactly $K$.

If you're determined to have your collection duplicate-free, add $n$ new elements $y_1,\ldots,y_n$, and the following sets: $$ \{y_1\},\{y_2\},\ldots,\{y_n\},\{y_1,y_2\},\{y_1,y_2,y_3\},\ldots,\{y_1,\ldots,y_n\}. $$ There are exact covers of the new elements of any size from $1$ to $n$.

$\endgroup$
  • $\begingroup$ I have edited the question, to make it more clear. Sorry for the confusion. $\endgroup$ – red31 May 26 at 13:24
  • 1
    $\begingroup$ Fortunately my answer already addresses this new version. $\endgroup$ – Yuval Filmus May 26 at 13:48
  • $\begingroup$ Sorry, I didn't quite understand your solution. I am going to sit down, and re-read it until it hopefully clicks. Thanks again for taking your time to respond! $\endgroup$ – red31 May 26 at 14:01
  • 1
    $\begingroup$ If you believe the proof then no example is needed... $\endgroup$ – Yuval Filmus May 26 at 14:50
  • 1
    $\begingroup$ Yes, your example demonstrates the construction nicely. $\endgroup$ – Yuval Filmus May 26 at 15:34

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.