A MIN-MAX THEOREM FOR A CONSTRAINED MATCHING PROBLEM.

The following constrained matching problem arises in the area of manpower scheduling. Consider an undirected graph G = (V, E) and a digraph D = (V, A). A master/slave-matching (MS-matching) in G with respect to D is a matching in G such that for each arc (u,v) ∈ A for which the node u is matched, the node v is matched too. The problem is to find an MS-matching of maximum cardinality. This paper addresses the special case where G is bipartite with bipartition V = W ∪ U and every (weakly) connected component of D is either an isolated node or two nodes in U which are joined by a single arc. The polyhedral structure of this special case is investigated and a min-max theorem which characterizes the cardinality of a maximum MS-matching in terms of the weight of a special node cover is derived. This min-max theorem includes as a special case the theorem of König. [ABSTRACT FROM AUTHOR]