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

Exact Cover


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.


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)


S = {1,2,3,4}

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


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


1 Answer 1


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

  • $\begingroup$ I have edited the question, to make it more clear. Sorry for the confusion. $\endgroup$
    – red31
    May 26, 2019 at 13:24
  • 1
    $\begingroup$ Fortunately my answer already addresses this new version. $\endgroup$ May 26, 2019 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, 2019 at 14:01
  • 1
    $\begingroup$ If you believe the proof then no example is needed... $\endgroup$ May 26, 2019 at 14:50
  • 1
    $\begingroup$ Yes, your example demonstrates the construction nicely. $\endgroup$ May 26, 2019 at 15:34

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.