3
$\begingroup$

Let $U$ be a finite set and $\mathcal O$ a set of subsets of $U$, how many subsets $\mathcal S$ of $\mathcal O$ satisfy the union of the elements of $\mathcal S$ is equal to $U$?

I think the problem of finding the smallest of these subsets is called the set cover problem, I can't find any reference to this structure though. Thanks in advance.

Regards.

$\endgroup$
1
  • $\begingroup$ I'm not sure what tags to use, feel free to tag appropriately $\endgroup$
    – Gorka
    Jul 17, 2014 at 0:05

5 Answers 5

2
$\begingroup$

EDITED:

Let $F({\cal O}, U)$ be the number of ways to cover $U$ using a multiset $\cal O$ of subsets of $U$ (so coverings using different versions of the same set are considered as different). Let $A$ be one element of $\cal O$, which occurs with multiplicity $k$ in $\cal O$. We can either include $A$ or not. If we do not include it, we then have to cover $U$ using ${\cal O} \backslash \{A^*\}$ (i.e. ${\cal O}$ with all occurrences of $A$ removed).
If we do include it, there are $2^k-1$ choices of which occurrences of $A$ in $\cal O$ to use for this, and then we have to cover the remaining points $U \backslash A$ using $\{B \backslash A\;:\; B \in {\cal O}\}$ (note that this can introduce additional multiplicity, because different $B$ can have the same $B \backslash A$). Thus

$$F({\cal O},U) = F({\cal O} \backslash \{A^*\},U) + (2^k-1) F(\{B \backslash A \; :\; B \in {\cal O}\}, U \backslash A) $$

with "boundary conditions" $$F({\cal O},U) = 0\ \text{if}\ U \backslash \bigcup {\cal O} \ne \emptyset $$ $$F(k \times \emptyset, U) = \cases{2^k & if $U = \emptyset$\cr 0 & otherwise\cr}$$ Of course the time this requires will generally be exponential in $|{\mathcal O}|$ (though not necessarily as bad as $2^{|{\mathcal O}|}$ if you are clever at caching and exploiting symmetry).

EDIT: Here is a Maple program that seems to work quite well in not-too-large examples.

F:= proc(Oh, Mult, m)
# m positive integer
# Oh a list of subsets of {1..m}
# Mult their multiplicities
# Returns number of ways to cover {1..m} using Oh with multiplicities Mult
option remember;
local mp, n, i, k, Aind, A, smax, M, Ohp, Ohs, V,F1,F2,
F1needed, Nocc,Multp, Multpp, unco, Psubs;

n:= nops(Oh);
if n = 0 then return 0 fi; 
Nocc:= [seq(numboccur(Oh,i),i=1..m)];
if has(Nocc,0) then 
  return 0 # can't cover elt 1
elif member(1,Nocc,'p') then 
# only one member of Oh covers p.  Need that one!
  F1needed:= false;
  Aind:= op(select(t -> has(Oh[t],p),[$1..nops(Oh)]));
    else # take a largest element A of Oh
      M:= [seq(nops(Oh[i]),i=1..n)];
      smax:= max(M);
      Aind:= min(select(t -> M[t]=smax, [$1..n]));
  F1needed:= true;
fi;
A:= Oh[Aind];
k:= Mult[Aind];
Ohp:= subsop(Aind=NULL,Oh);
Multp:= subsop(Aind=NULL,Mult);
if F1needed then # case where we don't use A
  F1:= F(Gperm(Ohp,m), Multp, m)
else
  F1:= 0;
fi;
# now consider the case where we do use A.
unco:= {$1..m} minus A;
    mp:= nops(unco);
    if mp = 0 then # nothing left to cover, so A at least once and any subset of the rest 
         return F1 + (2^k-1)*mul(2^Mult[j],j=1..n-1);
    fi;
    # map elts of Ohp to their unco images
    Psubs:= [seq(unco[i]=i,i=1..nops(unco))];
    Ohp:= map(S -> subs(Psubs, S intersect unco),Ohp);
    # now take account of multiplicity introduced
    Ohs:= convert(convert(Ohp,set),list);
    Multpp:= [0 $ nops(Ohs)];
for i from 1 to n-1 do
    member(Ohp[i],Ohs,'j');
    Multpp[j]:= Multpp[j]+Multp[i];
od:
F1 + (2^k-1)*F(Gperm(Ohs,mp), Multpp, mp);
end;
Gperm:= proc(Oh,m)
# return canonically permuted version of Oh
# sort 1..m in increasing order of number of occurrences in Oh
local Nocc,Perm,Psubs;
Nocc:= [seq(numboccur(Oh,i),i=1..m)];
Perm:= sort(Nocc,output='permutation');
Psubs:= zip(`=`,Perm,[$1..m]);
subs(Psubs,Oh);
end proc;

For example:

Oh:= convert(combinat:-powerset({$1..8}),list):
    Mult:= [1$nops(Oh)]:
F(Oh,Mult,8);

Result (in about 1/2 second):

$115792089237316195423570985008687907850547725730273056332267095982282337798562$

(which agrees with OEIS sequence A000371)

$\endgroup$
6
  • $\begingroup$ You need to mention that your recursion involves multisets, otherwise you get only a weak lower bound. $\endgroup$ Jul 17, 2014 at 17:27
  • $\begingroup$ Ah, good point. $\endgroup$ Jul 17, 2014 at 17:37
  • $\begingroup$ I like the edit. To hammer home the point, if you aren't using A, I recommend writing O\ {A*} to not be confused with removing a single instance of A, which I write as O\ {A}. The explanation is good, I'm just suggesting safety practices in notational use. $\endgroup$ Jul 17, 2014 at 18:24
  • $\begingroup$ Another good point. Done. $\endgroup$ Jul 17, 2014 at 18:41
  • $\begingroup$ Thank you very much, does this prove it cannot be calculated exponentially? $\endgroup$
    – Gorka
    Jul 17, 2014 at 18:56
5
$\begingroup$

If $\mathcal O$ is the set of all subsets of an $n$-element set $U$ then by inclusion-exclusion the number of subsets of $\mathcal O$ whose union is $U$ is $$\sum_{k=0}^n (-1)^{n-k} \binom nk 2^{2^k}.$$ This is sequence A000371 in the OEIS. I don't think there's any simple formula for an arbitrary set of subsets of $U$.

$\endgroup$
3
  • $\begingroup$ Thank you very much, so there isn't a simple formula for arbitrary $\mathcal O$? Is the problem NP hard? $\endgroup$
    – Gorka
    Jul 17, 2014 at 3:00
  • $\begingroup$ Do you know if the problem has been studied before? $\endgroup$
    – Gorka
    Jul 17, 2014 at 3:00
  • $\begingroup$ I don't know anything about the general problem. $\endgroup$
    – Ira Gessel
    Jul 17, 2014 at 3:19
2
$\begingroup$

If $\mathcal{O}$ consists of all subsets of size 2, then you are counting graphs without isolated vertices, see A006129.

My feeling is that in general this problem will be #P-hard, but don't ask me for a proof.

$\endgroup$
2
$\begingroup$

Well, if $\mathcal O$ is the set of all subsets of $U$ then there are $2^{2^u}$ subsets of $\mathcal O$, where $u$ is the cardinality of $U$, and most of these will have union equal to $U$. In fact, any subset whose union is not equal to $U$ has some element of $U$ consistently missing from its elements, hence there are at most $u\cdot 2^{2^{u-1}}$ (which is much less than $2^{2^u}$) many such.

This simple estimate in the case $u=5$ gives that among the 4,294,967,296 sets of subsets of $U=\{1,2,3,4,5\}$, at most 327,680 don't union up to $U$.

$\endgroup$
1
$\begingroup$

Let me reduce the general case for multisets to a possibly simpler case with a smaller underlying set. Let $F(f,X)$ denote how many submultisets of a multiset $f$ that cover $X$, and if $f:\mathcal{A}\rightarrow\mathbb{N}\setminus\{0\}$, then let $F(f)$ denote how many submultisets of $f$ have the same union as the union of the multiset $f$.

Suppose that $f:\mathcal{A}\rightarrow\mathbb{N}\setminus\{0\}$ is a multiset that covers $X$. Then define the specialization ordering $\leq_{\mathcal{A}}$ to be the preordering where $x\leq_{\mathcal{A}}y$ iff $y\in A\Rightarrow x\in A$. We say that $\mathcal{A}$ is $T_{0}$ if $\leq_{\mathcal{A}}$ is a partial ordering and $\mathcal{A}$ is $T_{1}$ if $\leq_{\mathcal{A}}$ is the partial ordering where $x\leq_{\mathcal{A}}y\Rightarrow x=y$ (i.e. $\leq_{\mathcal{A}}$ is the trivial partial ordering). The multiset $f$ is said to be $T_{0}$ or $T_{1}$ iff the domain $\mathcal{A}$ is respectively $T_{0}$ or $T_{1}$. I claim that calculating $F(f,X)$ easily reduces to the case where $f$ is $T_{1}$. And in case you were wondering, yes these are the topological separation axioms $T_{0}$ and $T_{1}$ generalized to a more general case.

It is easy to show that the general case reduces to the case where $\mathcal{A}$ is $T_{0}$. First, if $f:\mathcal{A}\rightarrow\mathbb{N}\setminus\{0\}$ is not $T_{0}$, then define $\simeq_{\mathcal{A}}$ to be the equivalence relation on $X$ where $x\simeq_{\mathcal{A}}y$ iff $x\leq_{\mathcal{A}}y$ and $y\leq_{\mathcal{A}}x$. Then let $\pi:X\rightarrow X/\simeq$ be the projection onto the quotient. Let $f':\{\pi[A]|A\in\mathcal{A}\}\rightarrow\mathbb{N}$ be the mapping where $f'(\pi[A])=f(A)$. Then it is easy to see that $F(f',X/\simeq_{\mathcal{A}})=F(f,X)$ and $\{\pi[A]|A\in\mathcal{A}\}$ is $T_{0}$.

Now suppose that $f:\mathcal{A}\rightarrow\mathbb{N}\setminus\{0\}$ and $\mathcal{A}$ is $T_{0}$. Then $\leq_{\mathcal{A}}$ is a partial ordering. Let $D$ be the collection of all maximal elements of the partial ordering $\leq_{\mathcal{A}}$. We take note that if $\mathcal{B}\subseteq\mathcal{A}$ and $\mathcal{B}$ covers $D$, then $\mathcal{B}$ covers all of $X$. If $x\in X$, then $x\leq_{\mathcal{A}}a$ for some $a\in D$. Therefore, there is some $B\in\mathcal{B}$ with $a\in B$. Therefore since $x\leq_{\mathcal{A}}a$, we have $x\in B$ as well. Therefore $\mathcal{B}$ truly covers all of $X$.

Let $f\wedge D$ be the multiset that corresponds to $\mathcal{A}\wedge D=\{A\cap D|A\in\mathcal{A}\}$ when we count multiplicity. In other words, $f(R)=\sum\{f(A)|A\in\mathcal{A},A\cap D=R\}$. Then we have $F(f\wedge D,D)=F(f,X)$. However, it is clear that the specialization ordering $\leq_{\mathcal{A}\wedge D}$ is the restriction of the specialization ordering $\leq_{\mathcal{A}}$ to $D$. However, $D$ is an antichain with respect to $\leq_{\mathcal{A}}$, so the partial ordering $\leq_{\mathcal{A}\wedge D}$ is trivial. Therefore $f\wedge D$ is truly a $T_{1}$ multiset.

At last, I claim that the problem is no more general when one considers multisets instead of simply sets. Suppose $(A_{i})_{i\in I}$ is a collection of sets that cover a set $X$. Without loss of generality, we can assume that $X\neq A_{i}$ for all $i\in I$. Then define $F((A_{i})_{i\in I})=|\{J\subseteq I|\bigcup_{j\in J}A_{j}=X\}|$. Then define $\mathcal{A}=\{A_{i}\cup I\setminus\{i\}|i\in I\}$. Then $\bigcup\mathcal{A}=X\cup I$, but the subsets of $\mathcal{A}$ that cover $X\cup I$ are in a one-to-one correspondence with the subsets $J$ of $I$ such that $X=\bigcup_{j\in J}A_{j}$.

$\endgroup$

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.