9
$\begingroup$

I am studying about set cover problem and wondering that which problems in real world can be solved by set cover. I found that IBM used this problem for their anti-virus problem, so there should be many more others that can be solved by set cover.

$\endgroup$
9
$\begingroup$

Set-cover heuristics are used in random testing ("fuzz testing") of programs. Suppose we have a million test cases, and we're going to test a program by picking a test case, randomly modifying ("mutating") it by flipping a few bits, and running the program on the modified test case to see if it crashes. We'd like to do this over and over again. If we do this naively, it will be less effective than it could be: typically many test cases cover basically the same code paths, but a small minority of test cases cover unusual code paths that would be interesting to test more intensively.

So, here's one solution that is used in industry. We use a coverage measurement tool to instrument the program and record which lines of code are covered by each of the million test cases. Then, we choose a small subset $S$ of those million test cases that has maximal coverage: every line of code covered by one of the million test cases will be covered by some test case in $S$. $S$ is called a reduced test suite. We then apply random mutation & testing to the reduced test suite $S$. Empirically, this seems to make random testing more effective. The smaller $S$ is, the more effective and efficient testing becomes.

So, how do we choose a reduced test suite $S$ that is as small as possible, while still achieving maximal coverage? Answer: that's a set cover problem, so we use standard heuristics/approximation algorithms for the set cover problem. The standard greedy approximation algorithm is typically used for this purpose.

| cite | improve this answer | |
$\endgroup$
5
$\begingroup$

Not sure if this is a real-world problem – solving sudokus can be reduced to an exact cover problem (note that exact cover is related to set cover, but not the same). You can find similar explanations here. Some fast solvers directly use Knuth's dancing links to solve sudokus, which is usually much faster than naive backtracking. However, the fastest solvers to date actually don't reduce sudoku solving to exact cover. They apply plain backtracking combined with advanced searching heuristics and careful code optimization.

| cite | improve this answer | |
$\endgroup$
3
$\begingroup$

By far the most relevant, large size, important application of set covering is in personnel shift planning (mainly in large airline companies). There, elements to be covered are the single shifts (or single flights), and sets are legal combinations of work/no work schedules. These easily go to millions or even billions of variables, as the number of combination is huge.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Hi, Fabio and welcome to the site! I edited your post to remove your signature, since posts here are automatically "signed" and the link to your group homepage wasn't directly relevant to your answer. But please do feel free to add that link to your profile page -- it would be completely appropriate there! $\endgroup$ – David Richerby Jan 8 '18 at 18:02
  • $\begingroup$ Could you please explain why this is a set cover problem? There must be one base set that needs to be covered, e.g. the set of all flights. But what are then the subsets that can be used for coverage? Probably there are some sort of local work/no work schedules, and each such work schedule determines a set of flights that is being covered? Then a number of such local work/no work schedules must be selected, such that each flight is covered exactly once, yielding a global work/no work schedule? $\endgroup$ – tillmo Jan 15 '19 at 8:46
0
$\begingroup$

Standard examples are the different variants of tiling problems. Given a grid of size $n\cdot m$ (possibly with some restrictions/forbidden squares) along with a set of objects (typically dominos pieces, L-shaped pieces or a a collection of pieces), is it possible to cover the grid (avoiding the restricted tiles) with objects without having to objects overlap.

Most variants can be easily reduced to exact cover (as mentioned in other answers a slightly modified version that requires all sets in the answer to be pairwise disjoint). Note that some of the variants are easier and can even be solved in O(1) as the case of a grid without restrictions and dominoes pieces.


Aside from that, minimum set cover occurs quite often in industry or as a daily life problem. Say you have a set of potential employees each with a set of skills and you need to select smallest poasible subset that covers all skills. Similarly, given a list of different kinds of fruits, each having its set of vitamins, what is the smallest set of different kinds of fruits covering all the vitamines you need, and so on.


Since you tagged graphs in your question, here are two applications of vertex-cover that might be interesting for you. Note that even though both problems are NP-complete, vertex cover is easier in the common sense, since it is a restricted case where each element in the universe appears in at most two subsets (each edge can be covered only by its endpoints).

In different areas of theoretical computer science, solving (bipartite) vertex-cover through bipartite matching algorithms is used as a subroutine. Here are two examples of which:

Kernalization techniques

Some kernalization techniques require computing a bipartite vertex-cover as a subroutine. For example Crown decomposition and the expansion lemma. Another standard example is the linear programming kernalization of vertex-cover itself.

As a reference see [Parameterized algorithms, Marek Cygan et al., 2015] or [Kernalization, Fedor V. Fomin et al., 2019].


Hardness proofs

Vertex-cover is one of the most studied problems. It is one of the easier NP-complete problems (Admitting approximation-algorithms, single exponential exact algorithms, etc..). These two facts make it one of the easiest problems to reduce when proving that a problem is NP-hard or that a problem does not admit certain running times unless ETH/SETH fail.

For NP-hard proofs I would refer to [Computers and intractability, Michael R. Garey and David S. Johnson, 1979] and to [Karp's 21 NP-Complete Problems]

For ETH and SETH you can refer to the same book of Cygan et al. refered above.

| cite | improve this answer | |
$\endgroup$

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.