HiveBrain v1.2.0
Get Started
← Back to all entries
debugMinor

Reduction from Exact Cover to Fixed Exact Cover

Submitted by: @import:stackexchange-cs··
0
Viewed 0 times
exactcoverreductionfixedfrom

Problem

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)

Solution

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

Context

StackExchange Computer Science Q#109836, answer score: 5

Revisions (0)

No revisions yet.