Content deleted Content added
Erel Segal (talk | contribs) Link to the category instead of individual pages |
Erel Segal (talk | contribs) |
||
Line 1:
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 [[Optimization (mathematics)|minimization problem]]s and usually [[linear programs]], whose [[dual problem]]s are called [[packing problem]]s.
The most prominent examples of covering problems are the [[set cover problem]], which is equivalent to the [[Hitting set|hitting set problem]], and its special cases, the [[vertex cover problem]] and the [[edge cover problem]].
Line 26 ⟶ 25:
For [[Petri net]]s, 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.
== {{Anchor|rainbow}}Rainbow covering and conflict-free covering ==
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:<ref>{{Cite journal|last=Arkin|first=Esther M.|last2=Banik|first2=Aritra|last3=Carmi|first3=Paz|last4=Citovsky|first4=Gui|last5=Katz|first5=Matthew J.|last6=Mitchell|first6=Joseph S. B.|last7=Simakov|first7=Marina|date=2018-12-11|title=Selecting and covering colored points|url=http://www.sciencedirect.com/science/article/pii/S0166218X18302695|journal=Discrete Applied Mathematics|language=en|volume=250|pages=75–86|doi=10.1016/j.dam.2018.05.011|issn=0166-218X}}</ref>
* 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-hardness|NP-hard]] (by reduction from [[linear SAT]]).
A more general notion is '''conflict-free covering'''.<ref>{{Cite journal|last=Banik|first=Aritra|last2=Sahlot|first2=Vibha|last3=Saurabh|first3=Saket|date=2020-08-01|title=Approximation algorithms for geometric conflict free covering problems|url=http://www.sciencedirect.com/science/article/pii/S0925772119301324|journal=Computational Geometry|language=en|volume=89|pages=101591|doi=10.1016/j.comgeo.2019.101591|issn=0925-7721}}</ref> In this problem:
* There is a set ''O'' of ''m'' objects, and a conflict-graph ''G<sub>O</sub>'' on ''O''.
* A subset ''Q'' of ''O'' is called ''conflict-free'' if it is an [[Independent set (graph theory)|independent set]] in ''G<sub>O</sub>'', that is, no two objects in ''Q'' are connected by an edge in ''G<sub>O</sub>''.
* A rainbow set is a conflict-free set in the special case in which ''G<sub>O</sub>'' 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<ref>{{Cite journal|last=Banik|first=Aritra|last2=Panolan|first2=Fahad|last3=Raman|first3=Venkatesh|last4=Sahlot|first4=Vibha|last5=Saurabh|first5=Saket|date=2020-01-01|title=Parameterized Complexity of Geometric Covering Problems Having Conflicts|url=https://doi.org/10.1007/s00453-019-00600-w|journal=Algorithmica|language=en|volume=82|issue=1|pages=1–19|doi=10.1007/s00453-019-00600-w|issn=1432-0541}}</ref> prove the following for the special case in which the conflict-graph has bounded [[arboricity]]:
* If the geometric cover problem is [[Fixed-parameter algorithm|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==
| |||