A constrained matching problem

We show that certain manpower scheduling problems can be modeled as the following constrained matching problem. Given an undirected graphG = (V,E) with edge weights and a digraphD = (V,A). AMaster/Slave-matching (MS-matching) ofG with respect toD is a matching ofG such that for each arc (u, v) A for which the nodeu is matched, the nodev is matched, too. TheMS-Matching Problem is the problem of finding a maximum-weight MS-matching. Letk(D) be the maximum size of a (weakly) connected component ofD. We prove that MS-matching is an NP-hard problem even ifG is bipartite andk(D) 3. Moreover, we show that in the relevant special case wherek(D) 2, the MS-Matching Problem can be transformed to the ordinary Matching Problem.This research was supported by Grant 03-KL7PAS-6 of the German Federal Ministry of Research and Technology.