1
$\begingroup$

I am trying to solve a problem which turns out to be a form of the set cover problem. I've implemented the greedy Set cover approximation algorithm for set cover, but it turns out to not be accurate enough for my needs.

Specifically I have a fixed, finite, list of special sets and I am trying to create a function which when given a set returns the smallest list of special sets which cover that given set, and that list should contain no sets which contain elements not in that given set. The fixed list seems like it should make the problem easier to solve than set cover, but I'm not sure how the additional requirement of no extra elements affects the difficulty. My sets also have a known maximum size which should also make this easier to solve.

A toy version of the problem is as follows:

Let $U$ be the set $\{a,b,c,d,e,f,g,h\}$. All the sets we mention from here on will be subsets of this set.

Let $S$ be a list of special sets. For this version of the problem we can use the following list:

$$ S = [\{a,b,c,d,e,f,g,h\}, \{a,b,c,d\}, \{e,f,g,h\}, \{a,e\}, \{b,f\}, \{c,g\}, \{d,h\}, \{a,b\}, \{b,c\}, \{c,d\}, \{d,e\}, \{e,f\}, \{f,g\},\{g,h\}, \{a\}, \{b\}, \{c\}, \{d\}, \{e\}, \{f\}, \{g\}, \{h\}]$$

For a given set $G$ what is the smallest list of sets which are part of $S$ which cover $G$, (that is where the union of the sets in the list is $G$).

For the above toy problem, the greedy approximation I've implemented, if presented with a set like $\{b, c, g, h\}$, produces $[\{c, g\}, \{b\}, \{h\}]$ instead of the smaller list $[\{b, c\}, \{g, h\}]$.

Has this sort of problem been well studied? Is there a known non-approximate algorithm given the additional constraints, that would be better than naive dynamic programming? A well-known name for the version of set cover where extra elements are not allowed would also be useful.

$\endgroup$
  • $\begingroup$ $[\{b, c\}, \{g, h\}]$? Is $\{b, c\}$ an element in $S$? $\endgroup$ – Apass.Jack Dec 25 '18 at 1:18
  • $\begingroup$ "which cover a given set" should be "each of which is a subset of a given set and all of which cover the given set". $\endgroup$ – Apass.Jack Dec 25 '18 at 1:19
  • 1
    $\begingroup$ Then to cover $\{b, c, g, h\}$, just one set is needed, $\{a,b,c,d,e,f,g,h\}$. $\endgroup$ – Apass.Jack Dec 25 '18 at 1:38
  • 1
    $\begingroup$ @Apass.Jack I don't want solutions that contain elements that are not in $G$ to be valid solutions. I've amended the question again. Thanks for making me state my question clearer! $\endgroup$ – Ryan1729 Dec 25 '18 at 6:54
  • 1
    $\begingroup$ Precompute the answer for every subset G of U. The total run time for the pre-computation is exponential in |U|, but since U is fixed, |U| is constant, so the time for the pre-computation is constant. Once you've done this, for a given G, just check in O(|G|) time whether G is a subset of U, and if it is, return the precomputed answer. Probably not what you want, but your problem is equivalent to set cover as I mention, so there isn't much you could do that is better, barring special structure in your sets S. $\endgroup$ – Neal Young Dec 27 '18 at 13:24
1
$\begingroup$

Your problem is hardly easier than the general set cover problem.

Given a set $G=\{b, c, g, h\}$, we remove all elements in $S$ that are not contained in $G$, obtaining a collection of set $C=[\{c,g\}, \{b,c\}, \{g,h\}, \{b\}, \{c\}, \{g\}, \{h\}]$. Now the problem becomes the standard set cover problem with $G$ being the universe and a collection of 7 subsets. Since this reduction process takes $O(n^2)$ time where $n$ is the total number of elements in $U$, your problem cannot not significant easier than the general set cover problem unless there are further conditions to be exploited.

Unfortunately, the general set cover problem is NP-hard. It is one of Karp's 21 NP-complete problems. Even more unfortunately, the simple greedy algorithm achieves about the best approximation ratio, $H(s')$, where $S'$ is the maximum cardinality of the sets. Here $H(n)$ is the $n$-th harmonic number.

If you have to obtain the exact minimum set cover, you will have to resort to exponential algorithms. One simple simplification that can be done is to remove all elements in $C$ that are subsets of another element of $C$. That is, we can replace $C$ by $[\{c,g\}, \{b,c\}, \{g,h\}]$. A simple brute force algorithm is just to test all subsets of $C$ of size 1, those of size 2, those of size 3, etc. A common way to attack the problem is by integer linear programming.

Just in case, you might want to take a look at some literature on the set cover problems. For example, An Exact Algorithm for Unicost Set Covering and LP techniques for set cover.

$\endgroup$
-1
$\begingroup$

I am trying to solve a problem that is some how similar to the set cover problem and would like to share my thoughts. What about trying an SMT solver or CSP solver?. However, I don't know yet if one of them would give better results

$\endgroup$
  • $\begingroup$ I’m attempting to solve this problem as part of another program, and I’d rather not add a general purpose solver as a dependency. ... But since I only need to solve the problem for one particular special list of sets, I might be able to get one of those solvers to produce a combat lookup table for me. I’ll look into that if no one else has a better suggestion. $\endgroup$ – Ryan1729 Dec 25 '18 at 0:56

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.