Near-Linear Algorithms for the k-colored Rainbow Sets

Abstrakt

In this paper, we address a variant of the minimum diameter color spanning set (MD-CSS) problem that is posed by Fleischer and Xu (2010). Let P be a set of n colored points. The MDCSS problem is to nd a subset of P that contains all the colors and admits the minimum possible diameter. Such a subset is called a rainbow (or color spanning) set. In this paper, we assume we need to find a rainbow set of size k, where k is smaller than the number of existing colors in P. We call this problem MDkCSS. We introduce an FPT algorithm for this problem, and we also discuss the enumeration and the decision version of the problem by introducing a reduction to all maximal independent sets of a bipartite graph. We also provide a 1.154-approximation algorithm for this problem. In the MDCSS problem, we prove that if the maximum frequency of the colors in P is bounded by 5, the problem remains NP-hard, which makes the conjecture that the number of existing colors in P is the parameter to determine the hardness of the MDCSS problem. Very recently, Pruente (2019) showed that the MDCSS problem is W[1]-hard if the number of the dimensions is not provided, and also introduced some exact algorithms with a quadratic dependency to the input size. Our FPT algorithm has a near-linear dependency on the number of points which sounds helpful to design a near-linear FPT for the MDCSS problem.