Covering problems

In combinatorics and computer science, covering problems are computational problems that ask whether a certain combinatorial structure 'covers' another, or how large the structure has to be to do that.

The most prominent examples of covering problems are the set cover problem, which is equivalent to the hitting set problem, and its special cases, the vertex cover problem and the edge cover problem.

In the context of linear programming, one can think of any minimization linear program as a covering problem if the coefficients in the constraint matrix, the objective function, and right-hand side are nonnegative.

[1] More precisely, consider the following general integer linear program: Such an integer linear program is called a covering problem if

Finally, an optimal solution to the above integer linear program is a covering of minimal cost.

There are various kinds of covering problems in graph theory, computational geometry and more; see Category:Covering problems.

Other stochastic related versions of the problem can be found.

[2] For Petri nets, the covering problem is defined as the question if for a given marking, there exists a run of the net, such that some larger (or equal) marking can be reached.

In particular, in the rainbow covering problem, each of the original objects has a "color", and it is required that the covering contains exactly one (or at most one) object of each color.

Rainbow covering was studied e.g. for covering points by intervals:[5] The problem is NP-hard (by reduction from linear SAT).

A more general notion is conflict-free covering.

[6] In this problem: Conflict-free set cover is the problem of finding a conflict-free subset of O that is a covering of P. Banik, Panolan, Raman, Sahlot and Saurabh[7] prove the following for the special case in which the conflict-graph has bounded arboricity:

The covering problem of Rado , where a series of squares with parallel edges needs to cover an area of 1. For any set meeting these conditions, a subset of these squares is selected (indicated by the red coloring) in which no two squares overlap, and the total area is maximized. The goal is to make an arrangement of squares so that the total area of the optimal subset is minimized . The examples each have maximal areas of 1/4, but there are some which have slightly lower. [ 3 ] [ 4 ]
The disk covering problem , which asks what the smallest real number is such that disks of radius can be arranged in such a way as to cover the unit disk.