×

On some matching problems under the color-spanning model. (English) Zbl 1429.68318

Summary: Given a set of \(n\) points \(Q\) in the plane, each colored with one of the \(k\) given colors, a color-spanning set \(S \subset Q\) is a subset of \(k\) points with distinct colors. The minimum diameter color-spanning set (MDCS) is a color-spanning set whose diameter is minimum. Somehow symmetrically, the largest closest pair color-spanning set (LCPCS) is a color-spanning set whose closest pair is the largest. Both MDCS and LCPCS have been shown to be NP-complete, but whether they are fixed-parameter tractable (FPT) when \(k\) is a parameter is open. Motivated by this question, we consider the FPT tractability of some matching problems under this color-spanning model, where 2\(k\) is the parameter. We show that the following three problems are polynomially solvable (hence FPT): (1) MinSum Matching Color-Spanning Set, (2) MaxMin Matching Color-Spanning Set, and (3) MinMax Matching Color-Spanning Set. For the \(k\)-Multicolored Independent Matching problem, namely, computing a matching of 2\(k\) vertices in a graph such that the vertices of the edges in the matching do not share edges, we show that it is W[1]-hard. Finally, motivated by this problem, which is related to the parameterized independent set problem, we are able to prove that LCPCS is W[1]-hard.

MSC:

68U05 Computer graphics; computational geometry (digital and algorithmic aspects)
68Q17 Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)
68Q27 Parameterized complexity, tractability and kernelization
68R10 Graph theory (including graph drawing) in computer science
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Abellanas, M.; Hurtado, F.; Icking, C.; Klein, R.; Langetepe, E.; Ma, L.; Palop, B.; Sacristan, V., Smallest color-spanning objects, (Proc. 9th European Symp. on Algorithms. Proc. 9th European Symp. on Algorithms, ESA’01 (2001)), 278-289 · Zbl 1006.68559
[2] Bereg, S.; Ma, F.; Wang, W.; Zhang, J.; Zhu, B., On the fixed-parameter tractability of some matching problems under the color-spanning model, (Proc. 11th Intl. Frontiers in Algorithmics Workshop. Proc. 11th Intl. Frontiers in Algorithmics Workshop, FAW’17 (2017)), 17-31
[3] Chen, Y.; Shen, S.; Gu, Y.; Hui, M.; Li, F.; Liu, C.; Liu, L.; Ooi, B. C.; Yang, X.; Zhang, D.; Zhou, Y., MarcoPolo: a community system for sharing and integrating travel information on maps, (Proc. 12th International Conference on Extending Database Technology. Proc. 12th International Conference on Extending Database Technology, EDBT’09 (2009)), 1148-1151
[4] Clark, B.; Colbourn, C.; Johnson, D., Unit disk graphs, Discrete Math., 86, 1-3, 165-177 (1990) · Zbl 0739.05079
[5] Downey, R.; Fellows, M., Parameterized Complexity (1999), Springer: Springer New York · Zbl 0914.68076
[6] Fan, C.; Luo, J.; Wang, W.; Zhong, F.; Zhu, B., On some proximity problems of colored sets, J. Comput. Sci. Tech., 29, 5, 879-886 (2014)
[7] Fellows, M.; Hermelin, D.; Rosamond, F.; Vialette, S., On the parameterized complexity of multiple-interval graph problems, Theoret. Comput. Sci., 410, 1, 53-61 (2009) · Zbl 1161.68038
[8] Fleischer, R.; Xu, X., Computing minimum diameter color-spanning sets, (Proc. 4th Intl. Frontiers of Algorithmics Workshop. Proc. 4th Intl. Frontiers of Algorithmics Workshop, FAW’10 (2010)), 285-292 · Zbl 1288.68115
[9] Fleischer, R.; Xu, X., Computing minimum diameter color-spanning sets is hard, Inform. Process. Lett., 111, 21-22, 1054-1056 (2011) · Zbl 1260.68153
[10] Flum, J.; Grohe, M., Parameterized Complexity Theory (2006), Springer-Verlag · Zbl 1143.68016
[11] Gabow, H., Implementation of Algorithms for Maximum Matching on Nonbipartite Graphs (1974), Stanford University, Ph.D. Thesis
[12] Gabow, H.; Tarjan, R., Algorithms for two bottleneck optimization problems, J. Algorithms, 9, 3, 411-417 (1988) · Zbl 0653.90087
[13] Ju, W.; Fan, C.; Luo, J.; Zhu, B.; Daescu, O., On some geometric problems of color-spanning sets, J. Comb. Optim., 26, 2, 266-283 (2013) · Zbl 1275.90080
[14] Lawler, E., Combinatorial Optimization: Networks and Matroids (1976), Holt, Rinehart & Winston: Holt, Rinehart & Winston New York · Zbl 0413.90040
[15] Ma, F.; Gao, X.; Yin, M.; Pan, L.; Jin, J-W.; Liu, H.; Zhang, J., Optimizing shortwave radio broadcast resource allocation via pseudo-Boolean constraint solving and local search, (Proc. 22nd Intl. Conf. on Principles and Practice of Constraint Programming. Proc. 22nd Intl. Conf. on Principles and Practice of Constraint Programming, CP’10 (2016)), 650-665
[16] Marx, D., Efficient approximation schemes for geometric problems?, (Proc. 13th European Symposium on Algorithms. Proc. 13th European Symposium on Algorithms, ESA’05 (2005)), 448-459 · Zbl 1162.68822
[17] Moser, H.; Sikdar, S., The parameterized complexity of the induced matching problem, Discrete Appl. Math., 157, 4, 715-727 (2009) · Zbl 1172.05350
[18] Moser, H.; Thilikos, D., Parameterized complexity of finding regular induced subgraphs, J. Discrete Algorithms, 7, 2, 181-190 (2009) · Zbl 1187.68351
[19] Preparata, F. P.; Shamos, M. I., Computational Geometry: An Introduction (1985), Springer-Verlag: Springer-Verlag New York, NY, USA · Zbl 0759.68037
[20] Zhang, D.; Chee, Y. M.; Mondal, A.; Tung, A. K.H.; Kitsuregawa, M., Keyword search in spatial databases: towards searching by document, (Proc. 25th IEEE International Conference on Data Engineering. Proc. 25th IEEE International Conference on Data Engineering, ICDE’09 (2009)), 688-699
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.