We study a variation of the assignment problem in operations research
and formulate it in terms of graphs as follows. Suppose G=(V,E) is a g
raph and U a subset of V.! A beta-assignment of G with respect to U is
an edge set X such that deg(X)(nu)=1 for all vertices nu in U, where
deg(X)(nu) is the degree of nu in the subgraph of G induced by the edg
e set X. The beta-assignment problem is to find a beta-assignment X su
ch that beta(X)=max {deg(X)(nu):nu is an element of V-U} is minimum. T
he purpose of this paper is to give an O(n(3))-time algorithm for the
beta-assignment problem in general graphs. As byproducts, we also obta
in a duality theorem as well as a necessary and sufficient condition f
or the existence of a beta-assignment for a general graph. The latter
result is a generalization of Tutte's theorem for the existence of a p
erfect matching of a general graph. (C) 1997 Elsevier Science Ltd.