Paper Info
Title
On the Fixed-Parameter Tractability of Some Matching Problems Under the Color-Spanning Model.
Abstract
Given a set of n points P in the plane, each colored with one of the t given colors, a color-spanning set S C P is a subset of t points with distinct colors. The minimum diameter color-spanning set (MDCS) is a color-spanning set whose diameter is minimum (among all color-spanning sets of P). Somehow symmetrically, the largest closest pair color-spanning set (LCPCS) is a color-spanning set whose closest pair is the largest (among all color-spanning sets of P). Both MDCS and LCPCS have been shown to be NP-complete, but whether they are fixed parameter tractable (FPT) when t is a parameter are still open. (Formally, the problem whether MDCS is FPT was posed by Fleischer and Xu in 2010.) Motivated by this question, we consider the FPT tractability of some matching problems under this color-spanning model, where t = 2k is the parameter. The results are summarized as follows: (1) Min Sum Matching Color-Spanning Set, namely, computing a matching of 2k points with distinct colors such that their total edge length is minimized, is FPT; (2) MaxMin Matching Color-Spanning Set, namely, computing a matching of 2k points with distinct colors such that the minimum edge length is maximized, is FPT; (3) MinMax Matching Color-Spanning Set, namely, computing a matching of 2k points with distinct colors such that the maximum edge length is minimized, is FPT; and (4) k-Multicolored Independent Matching, namely, computing a matching of 2k vertices in a graph such that the vertices of the edges in the matching do not share common edges in the graph, is W[1]-hard. With (2), we show that LCPCS is in fact FPT.
Year
DOI
Venue
2018
10.1007/978-3-319-59605-1_2
Lecture Notes in Computer Science
DocType
Volume
ISSN
Journal
10336
0302-9743
Citations 
PageRank 
References 
1
0.36
9
Authors
5
Name
Order
Citations
PageRank
Sergey Bereg124540.81
Feifei Ma25813.64
Wencheng Wang327037.99
Jian Zhang428824.45
Binhai Zhu5903109.96