What is Unique Coverage Problem?

Question

I am trying to understand the problem statement and the approximation algorithm for the Unique Coverage Problem from these notes. I have refined the question based on the comments provided. Thanks to D.W for pointing out Exact Cover problem.

Given a universe $U = \{ e_1, e_2, \dots, e_n\}$ of n elements and given a collection $\mathcal{S} = \{S_1, S_2, \dots, S_m\}$ of subsets of $U$ such that $\bigcup\limits_{S{_i}\in\mathcal{S}} S_i$, is equal to $U$.
Exact cover is a decisional problem of finding if there exists a sub-collection of subsets $\mathcal{S^{'}} \subseteq \mathcal{S}$, which can cover the Universe $U$ and each element $e \in U$ is contained exactly in one subset $s \in \mathcal{S^{'}}$.
Unique coverage problem is to find a sub-collection $\mathcal{S}^{'} \subseteq \mathcal{S}$, such that, pairwise intersection of $s \in \mathcal{S^{'}} = \phi$ and cardinality of $\bigcup\limits_{S{_i}\in\mathcal{S}} S_i$ is maximum.

My questions are,

1. Are the definitions written above correct?
2. Is the Unique Cover Problem a computational version of Exact Cover? (Exact cover requires universe $U$ to be completely covered, while Unique cover problem tries to maximize the cover of universe $U$).

From this video,I got the following example and answer for this example as 6, at duration 11:46.

$U = \{1,2,3,4,5,6,7,8\}$

$S_1 = \{1,2,5 \}$; $S_3 = \{1,5,6,7\}$
$S_2 = \{1,3,8 \}$; $S_4 = \{2,4,6,8\}$

It is also mentioned in the video that the answer is 6 and its when unique cover is $\{S_3, S_4\}$, but $\{S_3 \cap S_4\} = \{6\} \neq \phi$.

3. Isn't the answer to above example should be either $S_3$ or $S_4$, whose cardinality is 4?

The algorithm given in the notes is as following:

• Partition the elements into $\log n$ classes according to their degrees, i.e., the number of sets that cover the element. So class $i$ contains all the elements which are covered with at least $2^i$ and at most $2^{i+1}$ sets.
• Let $i$ be the class of the maximum cardinality.
• Choose any set with probability $\frac1{2^i}$

Applying the algorithm to above example, we get:

$class_1: \{3,4,7\}$; $class_2: \{2,5,6,8\}$; $class_3: \{1\}$

As cardinality of class 2 is maximum among others, we pick $i = 2$.

4. What does the algorithm mean to say,

   • Choose any set with probability $\frac1{2^i} = \frac1{4}$?
     (the probability of what?)

5. Can anyone explain how this algorithm will give a $\mathcal{O}(log \text{ }n)$ approximation of optimal solution?

Answer 1

Let's go over your questions one by one:

(1) Your definition of Unique cover is wrong. Given a set system $\mathcal{S}$, the goal is to find a subset $\mathcal{S}' \subseteq \mathcal{S}$ which uniquely covers the most elements. The subset $\mathcal{S}'$ uniquely covers an element $x$ if $x$ belongs to exactly one set in $\mathcal{S}'$.

(2) Exact cover is a decision problem, whereas Unique cover is an optimization problem. The decision version of Unique cover goes as follows:

Given a set system and an integer $k$, is there a subset of the set system which uniquely covers at least $k$ elements?

Exact cover is a special case of the decision version of Unique cover.

(3) The sets $S_3$ and $S_4$ together cover $6$ elements once ($1,2,4,5,7,8$). Since $6 > 4$, it is better to take both $S_3$ and $S_4$ rather than any of them individually.

(4) The probability is that of choosing any given set. I suggest you look for more material on probability theory and on randomized algorithms, and after that come back and see if it makes sense.

(5) This is explained very clearly in various lecture notes. There is no point repeating the explanation here. I suggest you learn probability theory and randomized algorithms from scratch, and then attempt to read the $O(\log n)$ analysis again. It might take a few weeks, but without catching up on the basics you have no chance of understanding anything which is even slightly advanced.