×

Minimum diameter color-spanning sets revisited. (English) Zbl 1506.90231

Summary: We address point sets in the \(d\)-dimensional space, in which every point is colored with at least one color out of the set \(C\). A Color-Spanning Set or Rainbow Set is a set of points that covers all colors of \(C\). The diameter of a set is the maximum distance between two points in the set. In this paper we answer some open questions about Minimum Diameter Color-Spanning Sets in \(d\)-dimensional space, which were studied by R. Fleischer and X. Xu [Lect. Notes Comput. Sci. 6213, 285–292 (2010; Zbl 1288.68115)], and extend this concept to general graphs. We show that the problem is W[1] hard for parameter \(|C|\) and not in PTAS if the number of dimensions is part of the input. Furthermore we demonstrate the membership in W[2]. Most importantly we present two exact solution methods, which both can also be used for the Largest Closest Color-Spanning Set Problem and compare them in an experimental evaluation. For general graphs we show that Minimum Diameter Color-Spanning Set Problem is NP-hard and W[1]-hard for parameter \(| C |\) but give a polynomial time algorithm for trees. In addition we develop a polynomial time 2-approximation algorithm for general graphs and prove that this problem admits no better approximation factor, unless \(P = N P\).

MSC:

90C27 Combinatorial optimization
05C62 Graph representations (geometric and intersection representations, etc.)
68Q17 Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)
68W25 Approximation algorithms

Citations:

Zbl 1288.68115

Software:

CPLEX
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Hassin, Refael; Tamir, Arie, On the minimum diameter spanning tree problem, Inform. Process. Lett., 531, 109-111 (1995), 01 · Zbl 0875.68442
[2] Ho, Jan-Ming; Lee, D.; Chang, Chia-Hsiang; Wong, C. K., Minimum diameter spanning trees and related problems, SIAM J. Comput., 20, 987-997 (1991), 10 · Zbl 0749.68042
[3] Ghodsi, Mohammad; Homapour, Hamid; Seddighin, Masoud, Approximate Minimum Diameter, 237-249 (2017), Springer International Publishing: Springer International Publishing Cham · Zbl 1434.68604
[4] Bereg, Sergey; Ma, Feifei; Wang, Wencheng; Zhang, Jian; Zhu, Binhai, On some matching problems under the color-spanning model, Theoret. Comput. Sci. (2018) · Zbl 1429.68318
[5] Fan, Cheng-Lin; Luo, Jun; Wang, Wen-Cheng; Zhong, Fa-Rong; Zhu, Binhai, On some proximity problems of colored sets, J. Comput. Sci. Tech., 29, 5, 879-886 (2014)
[6] Ju, Wenqi; Fan, Chenglin; Luo, Jun; Zhu, Binhai; Daescu, Ovidiu, On some geometric problems of color-spanning sets, J. Comb. Optim., 26, 2, 266-283 (2013) · Zbl 1275.90080
[7] Fleischer, Rudolf; Xu, Xiaoming, Computing Minimum Diameter Color-Spanning Sets, 285-292 (2010), Springer Berlin Heidelberg: Springer Berlin Heidelberg Berlin, Heidelberg · Zbl 1288.68115
[8] Kazemi, Mohammad Reza; Mohades, Ali; Khanteimouri, Payam, Approximation algorithms for color spanning diameter, Inform. Process. Lett., 135, 53-56 (2018) · Zbl 1476.68306
[9] Fellows, Michael R.; Hermelin, Danny; Rosamond, Frances; Vialette, Stéphane, On the parameterized complexity of multiple-interval graph problems, Theoret. Comput. Sci., 410, 1, 53-61 (2009) · Zbl 1161.68038
[10] Ibm ilog cplex optimizer 12.6. www.ibm.com/software/integration/optimization/cplex-optimizer, 2015.
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.