0
$\begingroup$

Given: Collection $C$ of Subsets of a finite set $S$, positive integer $K <=|C|$

Problem Statement: Is there a collection $B$ of subsets of $S$ with $|B| = K$ such that for each subset $c$ in $C$, there is a sub-collection in $B$ whose union is $c$ ?

This Set Basis Problem is NP-Complete.

If we enforce an additional constraint that $B$ is a subset of $C$, is the problem still NP Complete?

My assumption is yes, but I could not find any reference to this problem. Can anyone please point out to one?

$\endgroup$
3
$\begingroup$

The problem is in fact solvable in polynomial time.

Let $$C_0=\Bigl\{c\in C:c\supsetneq\bigcup_{\substack{c'\in C\\c'\subsetneq c}}c'\Bigr\}.$$

On the one hand, if $B\subseteq C$ has the property in the question, then $C_0\subseteq B$: since $c\in C_0$ cannot be written as the union of its proper subsets from $C$, a fortiori it cannot be written as a union of its proper subsets in $B$, hence the only possibility is $c\in B$.

On the other hand, $B=C_0$ does have the required property. We prove by induction on $|c|$ that any $c\in C$ is a union of a subcollection of $C_0$: if $c\in C_0$, this holds trivially; otherwise $c$ is the union of its proper subsets in $C$, which in turn can be written as unions of subcollections of $C_0$ by the induction hypothesis.

Thus, the problem is equivalent to $|C_0|\le K$, which can be checked in polynomial time.

$\endgroup$
  • $\begingroup$ Much thanks. I didn't get an answer here, thus the re-post at mathoverflow. I suppose deleting that should be ok? $\endgroup$ – TheoryQuest1 Apr 20 '17 at 12:45
  • $\begingroup$ You should wait at least several days before reposting a question. And whatever you do, always provide links in both directions between the posts. $\endgroup$ – Emil Jeřábek supports Monica Apr 20 '17 at 12:47

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.