Rainbow covering
An editor has nominated this article for deletion. You are welcome to participate in the deletion discussion, which will decide whether or not to retain it. |
Rainbow covering is a problem in computational geometry.
Definitions
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.
Hardness
The problem is NP-hard.[1] The proof is by reduction from linear SAT.
Generalization
Rainbow covering is a special case of the geometric conflict-free set cover problem.[2]
In this problem, there is a set O of m closed geometric 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.
Geometric 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[3] 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.
See also
References
- ^ 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.
- ^ 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.
- ^ 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.