Covering problems

From Wikipedia, the free encyclopedia
Jump to navigation Jump to search

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. Covering problems are minimization problems and usually linear programs, whose dual problems are called packing problems.

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.

General linear programming formulation[edit]

In the context of linear programming, one can think of any 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:

minimize
subject to
.

Such an integer linear program is called covering problem if for all and .

Intuition: Assume having types of object and each object of type has an associated cost of . The number indicates how many objects of type we buy. If the constraints are satisfied, it is said that is a covering (the structures that are covered depend on the combinatorial context). Finally, an optimal solution to the above integer linear program is a covering of minimal cost.

Kinds of covering problems[edit]

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

For Petri nets, for example, 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. Larger means here that all components are at least as large as the ones of the given marking and at least one is properly larger.

Rainbow covering and conflict-free covering[edit]

In some covering problems, the covering should satisfy some additional requirements. 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:[2]

  • There is a set J of n colored intervals on the real line, and a set P of points on the real line.
  • A subset Q of J is called a rainbow set if it contains at most a single interval of each color.
  • A set of intervals J is called a covering of P if each point in P is contained in at least one interval of Q.
  • The Rainbow covering problem is the problem of finding a rainbow set Q that is a covering of P.

The problem is NP-hard (by reduction from linear SAT).

A more general notion is conflict-free covering.[3] In this problem:

  • There is a set O of m objects, and a conflict-graph GO on O.
  • A subset Q of O is called conflict-free if it is an independent set in GO, that is, no two objects in Q are connected by an edge in GO.
  • A rainbow set is a conflict-free set in the special case in which GO is made of disjoint cliques, where each clique represents a color.

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[4] prove the following for the special case in which the conflict-graph has bounded arboricity:

  • If the geometric cover problem is fixed-parameter tractable (FPT), then the conflict-free geometric cover problem is FPT.
  • If the geometric cover problem admits an r-approximation algorithm, then the conflict-free geometric cover problem admits a similar approximation algorithm in FPT time.

References[edit]

  1. ^ Vazirani, Vijay V. (2001). Approximation Algorithms. Springer-Verlag. ISBN 3-540-65367-8.: 112 
  2. ^ Arkin, Esther M.; Banik, Aritra; Carmi, Paz; Citovsky, Gui; Katz, Matthew J.; Mitchell, Joseph S. B.; Simakov, Marina (2018-12-11). "Selecting and covering colored points". Discrete Applied Mathematics. 250: 75–86. doi:10.1016/j.dam.2018.05.011. ISSN 0166-218X.
  3. ^ Banik, Aritra; Sahlot, Vibha; Saurabh, Saket (2020-08-01). "Approximation algorithms for geometric conflict free covering problems". Computational Geometry. 89: 101591. doi:10.1016/j.comgeo.2019.101591. ISSN 0925-7721.
  4. ^ Banik, Aritra; Panolan, Fahad; Raman, Venkatesh; Sahlot, Vibha; Saurabh, Saket (2020-01-01). "Parameterized Complexity of Geometric Covering Problems Having Conflicts". Algorithmica. 82 (1): 1–19. doi:10.1007/s00453-019-00600-w. ISSN 1432-0541.