On the Fixed-Parameter Tractability of Some Matching Problems Under the Color-Spanning Model

DOI10.1007/978-3-319-59605-1_2zbMATH Open1430.68359arXiv1805.05448OpenAlexW2963030156MaRDI QIDQ4632199FDOQ4632199

Authors: Sergey Bereg, Feifei Ma, Wencheng Wang, Jian Zhang, Binhai Zhu 

Publication date: 26 April 2019

Published in: Frontiers in Algorithmics (Search for Journal in Brave)

Abstract: Given a set of $n$ points $P$ in the plane, each colored with one of the $t$ given colors, a color-spanning set $SsubsetP$ 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 is still open. 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 problems are summarized as follows: (1) MinSum Matching Color-Spanning Set, namely, computing a matching of $2k$ points with distinct colors such that their total edge length is minimized; (2) MaxMin Matching Color-Spanning Set, namely, computing a matching of $2k$ points with distinct colors such that the minimum edge length is maximized; (3) MinMax Matching Color-Spanning Set, namely, computing a matching of $2k$ points with distinct colors such that the maximum edge length is minimized; 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. We show that the first three problems are polynomially solvable (hence in FPT), while problem (4) is W[1]-hard.

Full work available at URL: https://arxiv.org/abs/1805.05448

Recommendations

• On some matching problems under the color-spanning model
• Minimum diameter color-spanning sets revisited
• On some geometric problems of color-spanning sets
• On some geometric problems of color-spanning sets
• On some proximity problems of colored sets

zbMATH Keywords

vertex coverundirected graphmatching problem

Mathematics Subject Classification ID

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

Cites Work

• Parameterized complexity of finding regular induced subgraphs
• Parametrized complexity theory.
• Linear degree extractors and the inapproximability of max clique and chromatic number
• Title not available (Why is that?)
• Title not available (Why is that?)
• On the parameterized complexity of multiple-interval graph problems
• Title not available (Why is that?)
• The parameterized complexity of the induced matching problem
• Computing minimum diameter color-spanning sets is hard
• On some geometric problems of color-spanning sets
• Computing minimum diameter color-spanning sets

Cited In (2)

• Budgeted colored matching problems
• On some matching problems under the color-spanning model

This page was built for publication: On the Fixed-Parameter Tractability of Some Matching Problems Under the Color-Spanning Model

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4632199)