Enumerating all set covers when knowing one set at least

Question

I have an index taking as keys values from the power set $P(S)$ of a set $S$, except for $\emptyset$ and $S$.

Then I have a query $Q=(s, k)$, where $s \in P(S) - \{\emptyset \cup S\}$ and $ 1 < k \le |S|$.

The result of the query is the set of covers $R$ of $S$; $\forall r \in R, |r| \le k$.

So for instance, if $S = \{a, b, c, d\}$ and $Q=( \{a,b\}, 3 )$, $R$ should return all covers of $S$ formed by $\{a, b\}$ and $k = (3 - 1 = ) 2$ or less other subsets of $P(S) - \{\emptyset \cup S\}$, namely: $R = \{$ $$ \{a,b\} , \{c\} , \{d\}$$ $$ \{a,b\} , \{c, d\} $$ $$ \{a,b\} , \{a, c, d\} $$ $$ \{a,b\} , \{b, c, d\} $$ $\}$

I want to know if there is an efficient algorithm that can give me all of these combinations of covers.

In other words, I want to know if there is an efficient way to get all covers formed by at most $k$ elements, where I only know 1 element out of k.

Answer 1

The first step is to eliminate the known set $s$. The idea is to find all covers of $S \setminus s$ using at most $k-1$ sets, and then augment the solution by adding all subsets of $s$ to all sets in any given cover in all possible ways. Details omitted.

For the new problem, it is enough to find all covers of $S$ of size exactly $k$ which don't use $S$ or $\emptyset$. In fact, we can ignore these restrictions, and just drop the (relatively) few solutions using these sets. We will generate them ordered, incurring a factor of $k!$ in efficiency; I'm sure that can be avoided, but I'll leave the details for you. Consider the sets $S_1,\ldots,S_k$ in order, and suppose that they cover $a_1,\ldots,a_k$ "new" elements, that is $|S_1| = a_1$, $|S_2 \setminus S_1| = a_2$ and so on. Then $a_1 + \cdots + a_k = |S|$, and we can enumerate over all such sequences (including zeroes). For each sequence, we can enumerate over the new elements themselves. Finally, we enumerate over all possible ways of adding "old" elements to sets, for example $S_3$ could additionally to $a_3$ new elements contain any subset of $S_1 \cup S_2$.