Rainbow covering

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
  1. 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.
  2. 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.
  3. 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.
This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.