0
$\begingroup$

As stated in the question, I'm interested in a variant of Exact Cover that is currently relevant to my research. Specifically, a variant where you are promised that if there is a Set Cover of size $k$, then there is also an Exact Cover of size $k$ (or less).

More formally, let us define the Exact Cover and Set Cover problems.

Set Cover Given a collection $S$ of of subsets $S_i$ of a set $X$ and a target $k$, does there exist a subcollection $S^{\ast}$ of $S$ of size $k$ or less such that every element in $X$ is contained in $S^{\ast}$?

Exact Cover Does there exist a Set Cover of size $k$ such that every element in $X$ is contained exactly once in $S^{\ast}$?

My modification is

Pure Exact Cover For a given input, categorize the input into one of two cases:

  1. There an Exact Cover of size $k$ or less,
  2. There is no Set Cover of size $k$.

You are promised that if there is a Set Cover of size $k$, there is also an Exact Cover of size $k$

Is this Pure Exact Cover problem still NP-hard? Or at least, has this problem been examined at all in the research? I can't find anything, but I also have no idea what name it would have.

$\endgroup$
1
  • 1
    $\begingroup$ This is a generalization of the NP-hard Perfect 3d Matching problem. $\endgroup$
    – Yonatan N
    Mar 8, 2023 at 0:20

1 Answer 1

5
$\begingroup$

It's also NP-hard, because Set Cover on sets of constant size is NP-hard, and given an instance of Set Cover with constant-size sets, you can add all the (polynomially many) subsets of the given sets, and you will obtain a new instance which is equivalent (has the same min-size set cover) but also has an exact cover of the same size as the min-size set cover.

$\endgroup$
1
  • $\begingroup$ Thank you! This is a really cute reduction that I'm kicking myself for not thinking of haha. $\endgroup$ Mar 8, 2023 at 5:04

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.