Constrained weighted matchings and edge coverings in graphs

We introduce the problem of finding a maximum weight matching in a graph such that the number of matched vertices lies in a prescribed interval and certain vertices will be matched. In the case of bipartite graphs, this generalizes the k-cardinality assignment problem which was recently studied by Dell'Amico and Martello. Similarly defined a minimum weight constrained edge covering problem is shown to be NP-hard even for bipartite graphs. We present a simple polynomial transformation of such matching and simplified covering problems to classical unconstrained problems. In the case of bipartite graphs also min-cost flow formulations are given.