# A variant of set cover problem reformulated

Given a universe set $U$ and $n$ sets of sets $A_i$ ($i=1, \cdots, n$). Each set $A_i$ contains $k_i$ subsets of $U$, i.e., $A_i=\{B_{ij}: j=1, \cdots, k_i\}$ where $B_{ij}$ is a subset of $U$. I have two questions. The first one is to find the minimum number of such $B_{i,j}$ to cover $U$ under the constraint that I can pick at most one such $B_{i,j}$ in each $A_i$. If such solution does not exist, my second question is to choose one set $B_{ij}$ from each set $A_i$ such that the union of the chosen sets covers the maximum number of elements in $U$.

• It seems like you have two tasks stated rather than questions - are you seeking an algorithm that does this as efficiently as possible? The setup is of interest to me, but as stated currently, I could be flip and say that you could simply exhaust all possible selections until you get a cover, and if you don't get a cover, go back over the list and see which selection(s) came the closest. – Thomas Rasberry Apr 3 '17 at 9:30
• @ThomasRasberry Thank you for the comment. Yes, I am seeking an efficient algorithm with polynomial complexity achieving bounded approximation ratio. Your algorithm is of exponential complexity. – lchen Apr 3 '17 at 9:54

The decision problem "Can $U$ be covered by sets $B_{ij}$ such that at most one set from each $A_i$ is used?" is NP-complete, and the optimization problem is APX-hard (there is a constant $c$ such that finding a $(1+c)$-approximation is NP-hard). This can be proved by reduction from 3-dimensional matching. Let $U=X\cup Y\cup Z$, and let the 3-DM instance be given by a set $T\subseteq X\times Y\times Z$. The corresponding instance of your problem has $n=\lvert U\rvert$, and the given collection of sets coonsists of the following: \begin{align*} A_x &= \{\{x,y,z\}\ :\ (x,y,z)\in T\} && x\in X,\\ A_y &= \{\{x,y,z\}\ :\ (x,y,z)\in T\} && y\in Y,\\ A_z &= \{\{x,y,z\}\ :\ (x,y,z)\in T\} && z\in Z. \end{align*}

• Thank you Thomas. Do you have any idea on possible approximation algorithm ($O(1)$ or even $O(log)$)? – lchen Apr 4 '17 at 8:18

The paper Maximizing a Monotone Submodular Function subject to a Matroid Constraint gives a $(1-1/e)$-approximation algorithm for a generalized version of your second question. Even in the case where all the $A_i$s are equal to each other, this approximation ratio is best possible under the assumption $P \ne NP$.

In order to put your second question into their framework, we set $X = \{B_{ij} : i \le n, j \le k_i\}$, define the monotone submodular function $f : 2^X \rightarrow \mathbb{R}_+$ by $f(S) = |\cup_{B_{ij} \in S} B_{ij}|$, and we define the matroid $\mathcal{M} = (X,I)$ to be a partition matroid: $S \subseteq X$ is independent iff $|S \cap A_i| \le 1$ for $i = 1, ..., n$. Then your goal is to maximize $f(S)$ over over the independent sets $S \in I$.