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 graph and U a subset of V. A &bgr;-assignment of G with respect to U is an edge set X such that degX(v)=1 for all vertices v in U, where degX(v) is the degree of v in the subgraph of G induced by the edge set X. The &bgr;-assignment problem is to find a &bgr;-assignment X such that &bgr;(X)≡max {degX(v):v∈V−U} is minimum. The purpose of this paper is to give an O(n3)-time algorithm for the &bgr;-assignment problem in general graphs. As byproducts, we also obtain a duality theorem as well as a necessary and sufficient condition for the existence of a &bgr;-assignment for a general graph. The latter result is a generalization of Tutte's theorem for the existence of a perfect matching of a general graph.
