Otdfbt

Why did Intel abandon unified CPU cache?

Should I refuse to be named as co-author of a low quality paper?

Ability To Change Root User Password (Vulnerability?)

Did Apple bundle a specific monitor with the Apple II+ for schools?

What differences exist between adamantine and adamantite in all editions of D&D?

Why is Na5 not played in this line of the French Defense, Advance Variation?

Can I utilise a baking stone to make crepes?

The origin of the Russian proverb about two hares

Is the use of umgeben in the passive unusual?

How to prove a 4D vector is a 4-Vector?

How do free-speech protections in the United States apply in public to corporate misrepresentations?

UTC timestamp format for launch vehicles

tabular: caption and align problem

Why are MBA programs closing in the United States?

Possible runaway argument using circuitikz

Java Servlet & JSP simple login

Should I put programming books I wrote a few years ago on my resume?

How to write a convincing religious myth?

Is it possible to have 2 different but equal size real number sets that have the same mean and standard deviation?

Electricity free spaceship

Getting UPS Power from One Room to Another

Separate SPI data

Does a bank have to tell me if a check made out to me was cashed there?

CircuiTikZ: How to draw contactor coil?

Reduction from Exact Cover to Fixed Exact Cover

Decision vs Optimization version for Problems of two ParametersHow to prove the NP-completeness of the ``Exact-3D-Matching`` problem by reducing the ``3-Partition`` problem to it?Log-Space Reduction $CO-2Col le_L USTCON$Need Help Reducing Subset Sum to Show a Problem is NP-CompleteReducing Exact Cover to Subset SumIs this a proof that SET COVER is not an NP-hard problem?Is the exact cover problem NP-hard when there is a restriction on the size?Reduction from Vertex CoverReduce EXACT 3-SET COVER to a Crossword PuzzleReducing Exact Cover to Subset Sum in practise!

5

1

$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 = x₁, x₂, ..., x_n (set)

P = P₁, P₂, ..., P_m (subsets of S)

Decision problem: Is there a subset P_i1,P_i2,...,P_iq of P such that every element of S belongs to exactly one of the P_ij:s?

Fixed Exact Cover

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

Decision problem: Is there a subset P_i1,P_i2,...,P_ik of P of size K such that every element of S belongs to exactly one of the P_ij: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 P_ij :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)

reductions np-hard

share|cite|improve this question

edited May 26 at 14:39

red31

asked May 25 at 11:20

red31red31

1326

$endgroup$

add a comment | 

5

1

$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 = x₁, x₂, ..., x_n (set)

P = P₁, P₂, ..., P_m (subsets of S)

Decision problem: Is there a subset P_i1,P_i2,...,P_iq of P such that every element of S belongs to exactly one of the P_ij:s?

Fixed Exact Cover

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

Decision problem: Is there a subset P_i1,P_i2,...,P_ik of P of size K such that every element of S belongs to exactly one of the P_ij: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 P_ij :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)

reductions np-hard

share|cite|improve this question

edited May 26 at 14:39

red31

asked May 25 at 11:20

red31red31

1326

$endgroup$

add a comment | 

$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 = x₁, x₂, ..., x_n (set)

P = P₁, P₂, ..., P_m (subsets of S)

Decision problem: Is there a subset P_i1,P_i2,...,P_iq of P such that every element of S belongs to exactly one of the P_ij:s?

Fixed Exact Cover

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

Decision problem: Is there a subset P_i1,P_i2,...,P_ik of P of size K such that every element of S belongs to exactly one of the P_ij: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 P_ij :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)

reductions np-hard

share|cite|improve this question

edited May 26 at 14:39

red31

asked May 25 at 11:20

red31red31

1326

$endgroup$

share|cite|improve this question

edited May 26 at 14:39

red31

asked May 25 at 11:20

red31red31

1326

share|cite|improve this question

edited May 26 at 14:39

red31

asked May 25 at 11:20

red31red31

1326

asked May 25 at 11:20

red31red31

1326

asked May 25 at 11:20

red31red31

1326

1 Answer
1

active

oldest

votes

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

share|cite|improve this answer

answered May 25 at 14:34

Yuval FilmusYuval Filmus

201k15194358

$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
  

  
  
  
  

 | 
show 3 more comments

Your Answer

StackExchange.ready(function()
var channelOptions =
tags: "".split(" "),
id: "419"
;
initTagRenderer("".split(" "), "".split(" "), channelOptions);

StackExchange.using("externalEditor", function()
// Have to fire editor after snippets, if snippets enabled
if (StackExchange.settings.snippets.snippetsEnabled)
StackExchange.using("snippets", function()
createEditor();
);

else
createEditor();

);

function createEditor()
StackExchange.prepareEditor(
heartbeatType: 'answer',
autoActivateHeartbeat: false,
convertImagesToLinks: false,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: null,
bindNavPrevention: true,
postfix: "",
imageUploader:
brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
allowUrls: true
,
onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
);



);

draft saved

draft discarded

Sign up or log in

StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);

Sign up using Google

Sign up using Facebook

Sign up using Email and Password

Post as a guest

Name

Email

Required, but never shown

StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fcs.stackexchange.com%2fquestions%2f109836%2freduction-from-exact-cover-to-fixed-exact-cover%23new-answer', 'question_page');

);

Post as a guest

Name

Email

Required, but never shown

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

share|cite|improve this answer

answered May 25 at 14:34

Yuval FilmusYuval Filmus

201k15194358

$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
  

  
  
  
  

 | 
show 3 more comments

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

share|cite|improve this answer

answered May 25 at 14:34

Yuval FilmusYuval Filmus

201k15194358

$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
  

  
  
  
  

 | 
show 3 more comments

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

share|cite|improve this answer

answered May 25 at 14:34

Yuval FilmusYuval Filmus

201k15194358

$endgroup$

share|cite|improve this answer

answered May 25 at 14:34

Yuval FilmusYuval Filmus

201k15194358

answered May 25 at 14:34

Yuval FilmusYuval Filmus

201k15194358

answered May 25 at 14:34

Yuval FilmusYuval Filmus

201k15194358