A constrained matching problem

The authors show that certain manpower scheduling problems can be modeled as the following constrained matching problem. Given an undirected graph G=(V,E) with edge weights and a digraph D=(V,A). A Master/Slave-matching (MS-matching) of G with respect to D is a matching of G such that for each arc (u,v)∈A for which the node u is matched, the node v is matched, too. The MS-Matching Problem is the problem of finding a maximum-weight MS-matching. Let k(D) be the maximum size of a (weakly) connected component of D. The authors prove that MS-matching is an NP-hard problem even if G is bipartite and k(D)∈3. Moreover, they show that in the relevant special case where k(D)∈2, the MS-Matching Problem can be transformed to the ordinary Matching Problem.