# Reduction from Exact Cover to Fixed Exact Cover

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.