Changing a given cover problem in R / C ++

Question

Given the universe of elements U = {1, 2, 3, ..., n} and the set of sets in this universe {S1, S2, ..., Sm}, what is the smallest set we can create that will cover at least one element in each of the m-sets?

For example, given the following elements U = {1,2,3,4} and the sets S = {{4,3,1}, {3,1}, {4}}, the following sets will cover at least one element from of each set: {1,4} or {3,4} therefore the required minimum size is 2.

Any thoughts on how this can be scaled to solve the problem with m = 100 or m = 1000 sets? Or thoughts on how to code this in R or C ++?

Sample data from above using the R library(sets) .

 s1 <- set(4, 3, 1) s2 <- set(3, 1) s3 <- set(4) s <- set(s1, s2, s3) 

Greetings

Answer 1

This is a problem with a set of tasks , which basically sets the cover with changing the roles of elements and sets. Referring to A = {4, 3, 1} and B = {3, 1} and C = {4}, the ratio of the restriction of the set of elements

  ABC 1 + + - 2 - - - 3 + + - 4 + - + 

therefore, you basically want to solve the problem of covering {A, B, C} with the sets 1 = {A, B} and 2 = {} and 3 = {A, B} and 4 = {A, C}.

Probably the easiest way to solve non-trivial instances of a set of covers in practice is to search for an integer programming package with an interface to R or C ++. Your example will be displayed as the next integer program in LP format.

 Minimize obj: x1 + x2 + x3 + x4 Subject To A: x1 + x3 + x4 >= 1 B: x1 + x3 >= 1 C: x4 >= 1 Binary x1 x2 x3 x4 End 

Answer 2

At first I misunderstood the complexity of the problem and came up with a function that finds a collection that covers m-sets, but then I realized that it is not necessarily the smallest:

 cover <- function(sets, elements = NULL) { if (is.null(elements)) { # Build the union of all sets su <- integer() for(si in sets) su <- union(su, si) } else { su <- elements } s <- su for(i in seq_along(s)) { # create set candidate with one element removed sc <- s[-i] ok <- TRUE for(si in sets) { if (!any(match(si, sc, nomatch=0L))) { ok <- FALSE break } } if (ok) { s <- sc } } # The resulting set s } sets <- list(s1=c(1,3,4), s2=c(1,3), s3=c(4)) > cover(sets) # [1] 3 4 

Then we can time:

 n <- 100 # number of elements m <- 1000 # number of sets sets <- lapply(seq_len(m), function(i) sample.int(n, runif(1, 1, n))) system.time( s <- cover(sets) ) # 0.53 seconds 

Not so bad, but still not the smallest.

The obvious solution: generate all the permutations of the elements and go to the coverage function and save the smallest result. This will approach "forever."

Another approach is to create a limited number of random permutations - this way you get an approximation of the smallest set.

 ns <- 10 # number of samples elements <- seq_len(n) smin <- sets for(i in seq_len(ns)) { s <- cover(sets, sample(elements)) if (length(s) < length(smin)) { smin <- s } } length(smin) # approximate smallest length 

Answer 3

If you limit each set to two elements, you have a problem with np-complete node. I would suggest that a more general problem would also be NP complete (for the exact version).

Answer 4

If you are just interested in an algorithm (and not an efficient / executable algorithm), you can simply generate subsets of a universe of increasing power and verify that the intersection with all the sets in S is not empty. Stop as soon as you get one that works; power may be minimal.

The complexity of this is 2 ^ | U | at worst, I think. Given the Foo Bah answer, I don't think you will get a polynomial time answer ...