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
bf3567d2da46e3dcbd34"" title=""Click to view the MathML source"" alt=""Click to view the MathML source"">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.
