On some matching problems under the color-spanning model

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 of 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 2k 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 2k 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. (C) 2018 Elsevier B.V. All rights reserved.