On some matching problems under the color-spanning model
On some matching problems under the color-spanning model
复制标题
DOI：
10.1016/j.tcs.2018.08.008
复制
发表时间：
2019-09
期刊：
影响因子：
--
通讯作者：
S. Bereg;Feifei Ma;Wencheng Wang;Jian Zhang;B. Zhu
中科院分区：
文献类型：
--
作者：
S. Bereg;Feifei Ma;Wencheng Wang;Jian Zhang;B. Zhu
给定平面上的一组n个点Q，每个点都用k个给定颜色中的一个着色，颜色生成集S Q是具有不同颜色的k个点的子集。最小直径色生成集是直径最小的色生成集。最大最近对颜色生成集（LCPCS）是一个最大的颜色生成集，它的最近对是最大的。MDCS和LCPCS都被证明是NP完全的，但当k是参数时，它们是否是固定参数可处理的（FPT）是开放的。基于这个问题，我们考虑了在这种颜色跨越模型下一些匹配问题的FPT易处理性，其中2k是参数。我们证明了以下三个问题是多项式可解的（因此是FPT）：（1）MinSum匹配颜色扩展集，（2）MaxMin匹配颜色扩展集，（3）MinMax匹配颜色扩展集。对于k-多色独立匹配问题，即计算图中2k个顶点的匹配，使得匹配中的边的顶点不共享边，我们证明了它是W [1]-困难的。最后，在这个与参数化独立集问题相关的问题的启发下，我们能够证明LCPCS是W [1]-困难的。
Given a set of n points Q in the plane, each colored with one of the k given colors, a color-spanning set S⊂ 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.