China & Japan: Nippon Kayaku – dyes
- 关键词：Matchings ; Perfect matchings ; Constraint programming ; NP-completeness ; Optimisation ; Hardness of approximation
- 刊名：Focus on Pigments
- 出版年：2008
- 期刊代码：94_09696210
- 类别：ce
- 出版时间：June 2008
- 卷：2008
- 期：6
- 页码：4
- 文件大小：51 K
摘要
Given a bipartite graph 
, an X-perfect matching is a matching in G that covers every node in X. In this paper we study the following generalisation of the X-perfect matching problem, which has applications in constraint programming: Given a bipartite graph as above and a collection 
of k subsets of X, find a subset M
E of the edges such that for each 
, the edge set M∩(C×D) is a C-perfect matching in G (or report that no such set exists). We show that the decision problem is NP-complete and that the corresponding optimisation problem is in APX when k=O(1) and even APX-complete already for k=2. On the positive side, we show that a 2/(k+1)-approximation can be found in poly(k,|X
D|) time. We show also that such an approximation M can be found in time 
, with the further restriction that each vertex in D has degree at most 2 in M.
E of the edges such that for each D|) time. We show also that such an approximation M can be found in time